单向链表
链表反转
判断是否有环,找链表的中间节点
快慢指针
找环的入口(求两个链表的交点可以转化成这个问题)
p1, p2 从 head 出发,p2 每次两步,p1 每次一步的方式走,发现 p2 和 p1 重合,确定了单向链表有环路。接下来,让 p2 回到链表的头部,重新走,每次步长不是走2了,而是走1,那么当 p1 和 p2 再次相遇的时候,就是环路的入口
双向链表
deque
双向链表可实现双端队列
例题
快慢指针
p1, p2 从 head 出发,p2 每次两步,p1 每次一步的方式走,发现 p2 和 p1 重合,确定了单向链表有环路。接下来,让 p2 回到链表的头部,重新走,每次步长不是走2了,而是走1,那么当 p1 和 p2 再次相遇的时候,就是环路的入口
双向链表可实现双端队列
例题