19. 删除链表的倒数第 N 个节点
141. 环形链表
142. 环形链表 II
160. 相交链表
19. 删除链表的倒数第 N 个节点
题目形容
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后，链表变为 1->2->3->5.
阐明：
给定的 n 保障是无效的。
进阶：
你能尝试应用一趟扫描实现吗？
思路
设置两个指针, 第一个向走 n 步, 而后两个指针一起往前走, 当第一个指针达到链表开端时, 第二个指针刚好指向倒数第 n 个元素
def removeNthFromEnd(head, n):
if n < 1 or head == None:
return head
p_fast = p_slow = head
# 快指针先往前挪动 n 步
for i in range(n):
p_fast = p_fast.next
# 如果此时 fast 指针为 None, 则要删除的节点为头节点
if p_fast == None:
return head.next
# 快慢指针同时后退
while p_fast.next != None:
p_fast = p_fast.next
p_slow = p_slow.next
p_slow.next = p_slow.next.next
return head工夫复杂度为 $O(n)$, 空间复杂度为 $O(1)$
141. 环形链表
给定一个链表，判断链表中是否有环。
为了示意给定链表中的环，咱们应用整数 pos 来示意链表尾连贯到链表中的地位（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。
示例 1：
输出：head = [3,2,0,-4], pos = 1 输入：true 解释：链表中有一个环，其尾部连贯到第二个节点。
示例 2：
输出：head = [1,2], pos = 0 输入：true 解释：链表中有一个环，其尾部连贯到第一个节点。
示例 3：
输出：head = [1], pos = -1 输入：false 解释：链表中没有环。
进阶：
你能用 O(1)（即，常量）内存解决此问题吗？
一个直观的想法是应用字典记录每个节点的拜访状态, 如果曾经被拜访, 则返回 False
def hasCycle(head):
if not head:
return False
dicts = {}
while head:
if head in dicts:
return True
dicts[head] = 1
head = head.next
return False工夫复杂度为 $O(n)$, 空间复杂度为 $O(n)$
思路 2, 双指针
设置 2 个速度不一样的指针, 别离为 p1 和 p2, p1 每次前进一步, p2 每次后退 2 步.
如果链表中不蕴含环, 则 p2 会先达到起点, 此时完结, 返回 False
如果链表蕴含环, 则 p2 最初会赶上 p1, 此时完结, 返回 True
def hasCycle(head):
if (not head) or (not head.next):
return False
p1 = head
p2 = head.next
while p1 != p2:
p1 = p1.next
if not p2 or not p2.next:
return False
p2 = p2.next.next
return True工夫复杂度为 $O(n)$, 空间复杂度为 $O(1)$
142. 环形链表 II
给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。
为了示意给定链表中的环，咱们应用整数 pos 来示意链表尾连贯到链表中的地位（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。
阐明：不容许批改给定的链表。
示例 1：
输出：head = [3,2,0,-4], pos = 1 输入：tail connects to node index 1 解释：链表中有一个环，其尾部连贯到第二个节点。
示例 2：
输出：head = [1,2], pos = 0 输入：tail connects to node index 0 解释：链表中有一个环，其尾部连贯到第一个节点。
示例 3：
输出：head = [1], pos = -1 输入：no cycle 解释：链表中没有环。
进阶：你是否能够不必额定空间解决此题？
和上题一样, 同样能够应用字典来解决
def detectCycle(head):
if not head or not head.next:
return None
dicts = {}
p = head
while p:
if p in dicts:
return p
else:
dicts[p] = 0
p = p.next
return None工夫复杂度为 $O(n)$, 空间复杂度为 $O(n)$
思路 2
如下图所示, 最右边红色节点示意链表的起始节点 p_start, 两头红色节点示意环形链表的入口节点 p_entrance, 左边红色节点示意快慢节点第一次相遇的节点 p_inter.
p_start 到 p_entrance 之间的间隔为 F, p_entrance 到 p_inter 之间的间隔为 a, p_inter 到 p_entrance 之间的间隔为 b.
快慢指针同时后退, 在 p_iter 相遇, 则有如下公式成立
$2(F+a) = (F+a+b + a) + 1$
即失去
$F=b+1$
def detectCycle(head):
if not head or not head.next:
return None
#设置快慢指针, 快指针是从第二个节点登程
fast = head.next
slow = head
# has_cycle =
inter_node = None
# 快指针和慢指针同时登程
while fast and fast.next:
# 当快指针和慢指针指向同一地位时, 退出循环
if fast == slow:
inter_node = fast
break
fast = fast.next.next
slow = slow.next
# 如果 inter_node 为 None, 阐明无环
if not inter_node:
return None
fast = head
slow = inter_node.next
while fast != slow:
fast = fast.next
slow = slow.next
return slow总体的思路
- 设置快指针 (每次走 2 步) 和慢指针(每次走 1 步), 同时登程, 如果最初快指针和慢指针指向同一地位, 阐明有环.
- 将快指针后移一个节点, 慢指针指向 head 节点, 而后同时以雷同的速度登程.
- 直至相遇, 返回相遇节点.
160. 相交链表
编写一个程序，找到两个单链表相交的起始节点。
如上面的两个链表：
在节点 c1 开始相交。
示例 1：
输出：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 输入：Reference of the node with value = 8 输出解释：相交节点的值为 8（留神，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
示例 2：
输出：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1 输入：Reference of the node with value = 2 输出解释：相交节点的值为 2（留神，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
示例 3：
输出：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 输入：null 输出解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。因为这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 能够是任意值。解释：这两个链表不相交，因而返回 null。
留神：
如果两个链表没有交点，返回 null. 在返回后果后，两个链表仍须放弃原有的构造。可假定整个链表构造中没有循环。程序尽量满足 O(n) 工夫复杂度，且仅用 O(1) 内存。
思路 1: 应用堆栈
def getIntersectionNode(headA: ListNode, headB: ListNode):
if not headA or not headB:
return None
stacka = []
stackb = []
pa = headA
pb = headB
# 将链表 a 所有节点入栈
while pa:
stacka.append(pa)
pa = pa.next
# 将链表 b 所有节点入栈
while pb:
stackb.append(pb)
pb = pb.next
res = None
pa = stacka.pop()
pb = stackb.pop()
# 顺次出栈
while pa == pb:
res = pa
if not stacka or not stackb:
break
pa = stacka.pop()
pb = stackb.pop()
return res工夫复杂度 $O(m+n)$, 空间复杂度 $O(m+n)$
思路 2:
应用字典
def getIntersectionNode(headA: ListNode, headB: ListNode):
if not headA or not headB:
return None
dicts = {}
pa = headA
while pa:
dicts[pa] = 1
pa = pa.next
pb = headB
while pb:
# 如果该节点曾经在字典中, 则能够间接返回
if pb in dicts:
return pb
pb = pb.next
return None工夫复杂度为 $O(m+n)$, 空间复杂度为 $O(m)$ 或 $O(n)$
思路 3
双指针
- 设置指针 p1, p2 别离在 headA 和 headB 上挪动
- 如果 p1 指向 None, 则将 p1 指向 headB 持续遍历
- 如果 p2 指向 None, 则将 p2 指向 headA 持续遍历
- 如果 p1 和 p2 指向的节点雷同, 且不为 None, 则找到了相交节点
在遍历的过程中, 两个指针为了放弃同一进度, 打消长度差. 当较长的链表指针指向较短链表 head 时, 长度差就能够打消
def getIntersectionNode(headA: ListNode, headB: ListNode):
if not headA or not headB:
return None
p1 = headA
p2 = headB
while p1 != p2:
p1 = headB if not p1 else p1.next
p2 = headA if not p2 else p2.next
return p1最初遍历的次数为, 工夫复杂度为 $O(m+n)$, 空间复杂度为$O(1)$
总结
这里介绍了几道对于快慢指针的题目, 快慢指针在链表中非常常见, 尤其是遇到环形链表, 穿插链表等这类问题时, 都能够应用快慢指针来解决问题. 它们的思路通常都是利用门路差来失去要害节点地位, 从而求解问题.