LeeCode 19: 删除链表的倒数第n个节点
题目描述：
给你一个链表，删除链表的倒数第
n个节点，并返回链表的头节点。
标签：链表，双指针
时间复杂度：O(N)
建立模型：
- 定义虚拟头节点，使其 next 指向 head
定义快慢指针 fast，slow，slow指向虚拟头节点，fast指向第 n 个节点
同时移动 fast，slow，直至 fast 到达链表尾部
此时 slow 的 next 域指向的节点即是要删除的节点
删除 slow.next，并返回虚拟头节点的 next 域
定义虚拟头节点的目的是便于将头节点与其它节点一样处理，无需额外讨论。
代码实现：
# Python3 实现
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
virtualHead = ListNode(0, head)
slow, fast = virtualHead, virtualHead
for _ in range(n):
fast = fast.next
while fast.next:
slow, fast = slow,next, fast.next
slow.next = slow.next.next
return virtualHead.next
// Java 实现
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode virtualHead = new ListNode(0, head);
ListNode fast = virtualHead;
ListNode slow = virtualHead;
while (n > 0) {
fast = fast.next;
n -= 1;
}
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return virtualHead.next;
}
LeeCode 02.07: 链表相交
题目描述：
给你两个单链表的头节点
headA和headB，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，则返回null。
标签：链表，双指针
时间复杂度：O(M+N)
建立模型：
- 假设链表 headA 长度为a，链表 headB 长度为b，链表相交长度为c
遍历完 headA 再遍历 headB，到起始公共节点，共经过 a + (b - c + 1) 个节点
遍历完 headB 再遍历 headA，到起始公共节点，共经过 b + (a - c + 1) 个节点
若 c = 0，即不存在公共节点，则当前节点 a，b 均指向
Null若 c > 0，即存在公共节点，则当前节点 a，b 指向起始公共节点
代码实现：
# Python3 实现
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
a, b = headA, headB
# a == b 存在两种情况
# 1. a = null, b = null, 即两指针均将 headA 和 headB 遍历完也没有相遇
# 2. a = c1, b = c1, 即两指针遍历过程中在链表相交起始节点相遇
while a != b:
a = a.next if a else headB
b = b.next if b else headA
return a
// Java 实现
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode a = headA;
ListNode b = headB;
while (a != b) {
a = (a == null ? headB : a.next);
b = (b == null ? headA : b.next);
}
return a
}
LeeCode 142: 环形链表 II
题目描述：
给你一个链表的头节点
head，返回链表开始入环的第一个节点，如果链表无环则返回null。
标签：链表，双指针
时间复杂度：O(N)
建立模型：
设 链表头部到环之前有 a 个节点, 链表环内有 b 个节点
定义快慢指针 fast, slow ，fast每次走两步，slow每次走一步
若 fast 走到链表尾部，则说明链表无环 return null
若 fast 与 slow 相遇，则 fast 与 slow 走过的路程关系有：
\[\begin{cases}
fast = 2 * slow \\
fast - slow = n * b
\end{cases}
\qquad
\Rightarrow
\qquad
\begin{cases}
fast = 2 * n * b \\
slow = n * b
\end{cases}
\]
且 slow 指针每次走到链表环的第一个节点时步数表达式为：\(slow = a + n * b\)
所以 slow 与 fast 相遇后再走 a 步即可到达链表环的第一个节点
如何确定 a 呢？
将 fast 指针重新指向 head，head 走 a 步也到达链表环的第一个节点，即同时移动 fast 和 slow，直至其第二次相遇
代码实现：
# Python 3实现
def detectCycle(self, head: ListNode) -> ListNode:
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
break
if not (fast and fast.next):
return None
fast = head
while fast != slow:
slow, fast = slow.next, fast.next
return slow
// Java 实现
public ListNode detectCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
break;
}
}
if (fast == null || fast.next == null) {
return null;
}
fast = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
