目录
链表
链表相关的典型应用如下：
| 序号 | 题目 |
|---|---|
| 1 | 21. 合并两个有序链表 |
| 2 | 23. 合并 K 个升序链表 |
| 3 | 141. 环形链表 |
| 4 | 142. 环形链表 II |
| 5 | 876. 链表的中间结点 |
| 6 | 160. 相交链表 |
| 7 | 19. 删除链表的倒数第 N 个结点 |
应用
应用1：Leetocde.21
题目
分析
定义一个虚节点 \(dummy\)，然后开始遍历两个链表，每次将两个链表中较小的节点连接到新链表上，并后移动当前链表的指针。
遍历完后，如果两个链表的长度不相等，将剩余链表直接连接到新链表上。
代码实现
方法一：迭代实现
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
return self.merge(list1, list2)
def merge(self, left: ListNode, right: ListNode):
""" 迭代实现 """
dummy = ListNode(-1)
node = dummy
while left and right:
if left.val < right.val:
node.next = left
left = left.next
else:
node.next = right
right = right.next
node = node.next
if not left:
node.next = right
else:
node.next = left
return dummy.next
方法一：递归实现
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
return self.merge(list1, list2)
def merge(self, left: ListNode, right: ListNode):
""" 递归实现 """
if not left:
return right
if not right:
return left
if left.val < right.val:
left.next = self.merge(left.next, right)
return left
else:
right.next = self.merge(left, right.next)
return right
应用2：Leetocde.23
题目
分析
方法一：分治
使用分治的思想，将原链表数组拆分，将多个链表的合并，转换为合并两个链表的问题。
方法二：优先级队列
代码实现
把链表的头结点放进一个小根堆，这样堆顶的元素始终是最小的元素，只需要每次弹出一个元素，即最小元素，如果它还有后驱节点，则将其放回小根堆。
方法一：分治
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
return self.merge(lists, 0, len(lists) - 1)
def merge(self, lists, left: int, right: int):
if left == right:
return lists[left]
if left > right:
return None
mid = (left + right) // 2
return self.merge_2_lists(self.merge(lists, left, mid), self.merge(lists, mid + 1, right))
def merge_2_lists(self, list1: ListNode, list2: ListNode):
if list1 is None:
return list2
if list2 is None:
return list1
dummy = ListNode()
p = dummy
p1 = list1
p2 = list2
while p1 and p2:
if p1.val < p2.val:
p.next = p1
p1 = p1.next
else:
p.next = p2
p2 = p2.next
p = p.next
if p1:
p.next = p1
if p2:
p.next = p2
return dummy.next
方法二：优先级队列
class Solution {
ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0) {
return null;
}
// 虚拟头结点
ListNode dummy = new ListNode(-1);
ListNode p = dummy;
// 优先级队列，最小堆
PriorityQueue<ListNode> pq = new PriorityQueue<>(
lists.length, (a, b)->(a.val - b.val)
);
// 将 k 个链表的头结点加入最小堆
for (ListNode head : lists) {
if (head != null)
pq.add(head);
}
while (!pq.isEmpty()) {
// 获取最小节点，接到结果链表中
ListNode node = pq.poll();
p.next = node;
// 如果当前节点还有next节点，将其放回小根堆
if (node.next != null) {
pq.add(node.next);
}
// p 指针不断前进
p = p.next;
}
return dummy.next;
}
}
应用3：Leetocde.141
题目
分析
使用快慢指针即可，慢指针走一步，快指针走两步，如果快慢指针相遇，则链表存在环，否则就不存在环。
代码实现
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
if not head or not head.next:
return False
slow = head
fast = head.next
while slow != fast:
if not fast or not fast.next:
return False
slow = slow.next
fast = fast.next.next
return True
应用4：Leetocde.142
题目
分析
算法步骤：
-
使用快慢指针 \(slow\) 和 \(fast\)，分别指向链表的头节点；
-
遍历链表，慢指针走一步，快指针走两步，当两者相遇时，则停止遍历；
-
如果快指针 \(fast\) 指向空节点或者 \(fast\) 的下一个节点为空节点，则不存在环；
-
否则，重新让慢指针 \(slow\) 指向头节点，\(fast\) 指针从当前位置开始移动，如果两者相遇，则相遇的位置就是环的起点。
-
代码实现
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast, slow;
fast = slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
break;
}
}
if (fast == null || fast.next == null) {
// fast 遇到空指针说明没有环
return null;
}
// 重新指向头结点
slow = head;
// 快慢指针同步前进，相交点就是环起点
while (slow != fast) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
应用5：Leetocde.876
题目
分析
使用快慢指针的思路，即慢指针走一步，快指针走两步，当快指针走到链表末尾时，慢指针就指向链表中点。
代码实现
class Solution {
public ListNode middleNode(ListNode head) {
// 快慢指针初始化指向 head
ListNode slow = head, fast = head;
// 快指针走到末尾时停止
while (fast != null && fast.next != null) {
// 慢指针走一步，快指针走两步
slow = slow.next;
fast = fast.next.next;
}
// 慢指针指向中点
return slow;
}
}
应用6：Leetocde.160
题目
分析
代码实现
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> 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
应用7：Leetocde.19
题目
分析
算法思路：
-
先通过双指针的思路，找到倒数第 \(n + 1\) 个节点，即待删除节点的前一个节点；
查找倒数的 \(k\) 个节点的思路：
-
使用两个指针
p1和p2，同时指向头节点； -
先让
p1先移动 k 步； -
让
p1和p2同时后移，直到p1移动到链表末尾。
-
-
删除倒数第 \(n + 1\) 个节点的下一个节点；
代码实现
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
if not head:
return head
dummy = ListNode(-1, head)
# 找到倒数第n+1个节点
node = self.findFromEnd(dummy, n + 1)
node.next = node.next.next
return dummy.next
def findFromEnd(self, head: ListNode, k) -> ListNode:
""" 找到链表的倒数第k个节点 """
p1 = head
# p1先移动k步
for i in range(k):
p1 = p1.next
p2 = head
# p2移动 n - k 步
while p1:
p1 = p1.next
p2 = p2.next
return p2
def removeNthFromEnd2(self, head: ListNode, n: int) -> ListNode:
dumy = ListNode(-1, head)
fast, slow = head, dumy
for i in range(n):
fast = fast.next
while fast:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return dumy.next
参考：
标签：slow,ListNode,fast,next,链表,应用,return,III From： https://www.cnblogs.com/larry1024/p/17425167.html