快慢指针：链表题目的利器

快慢指针：链表题目的利器

1. 快慢指针的根本概念

快慢指针是一种双指针本领，通常用于办理链表题目。它利用两个指针，一个指针（慢指针）每次移动一步，另一个指针（快指针）每次移动两步。通过这种移动方式，快指针的移动速率是慢指针的两倍，因此快指针会先到达链表的末了。
2. 快慢指针的利用场景

2.1 探求链表的中心节点

这是快慢指针最常见的应用场景之一。通过快慢指针，可以轻松找到链表的中心节点。当快指针到达链表末了时，慢指针恰好位于链表的中心位置。
示例代码：

1. ListNode *middleNode(ListNode *head) {
2.     if (head == NULL || head->next == NULL) {
3.         return head;
4.     }
6.     ListNode *fast = head, *slow = head;
7.     while (fast->next != NULL && fast->next->next != NULL) {
8.         slow = slow->next;
9.         fast = fast->next->next;
10.     }
11.     if (fast->next != NULL) {
12.         slow = slow->next;
13.     }
15.     return slow;
16. }

复制代码

2.2 检测链表中的环

快慢指针也可以用于检测链表中是否存在环。假如链表中存在环，快指针和慢指针终极会在环内相遇。假如快指针到达链表末了，则链表中不存在环。
示例代码：

1. bool hasCycle(ListNode *head) {
2.     if (head == NULL || head->next == NULL) {
3.         return false;
4.     }
6.     ListNode *fast = head, *slow = head;
7.     while (fast->next != NULL && fast->next->next != NULL) {
8.         slow = slow->next;
9.         fast = fast->next->next;
10.         if (slow == fast) {
11.             return true;
12.         }
13.     }
15.     return false;
16. }

复制代码

2.3 探求环的入口

假如链表中存在环，快慢指针还可以用于找到环的入口。当快指针和慢指针在环内相遇后，将此中一个指针重置为链表头，然后两个指针每次各移动一步，它们再次相遇的位置即为环的入口。
示例代码：

1. ListNode *detectCycle(ListNode *head) {
2.     if (head == NULL || head->next == NULL) {
3.         return NULL;
4.     }
6.     ListNode *fast = head, *slow = head;
7.     while (fast->next != NULL && fast->next->next != NULL) {
8.         slow = slow->next;
9.         fast = fast->next->next;
10.         if (slow == fast) {
11.             break;
12.         }
13.     }
15.     if (fast->next == NULL || fast->next->next == NULL) {
16.         return NULL;
17.     }
19.     slow = head;
20.     while (slow != fast) {
21.         slow = slow->next;
22.         fast = fast->next;
23.     }
25.     return slow;
26. }

复制代码

2.4 探求链表的倒数第 k 个节点

快慢指针可以用于找到链表的倒数第 k 个节点。起首，将快指针向前移动 k 步，然后快慢指针同时移动，当快指针到达链表末了时，慢指针恰好位于倒数第 k 个节点。
示例代码：

1. ListNode *findKthToLast(ListNode *head, int k) {
2.     if (head == NULL) {
3.         return NULL;
4.     }
6.     ListNode *fast = head, *slow = head;
7.     for (int i = 0; i < k; i++) {
8.         if (fast == NULL) {
9.             return NULL;
10.         }
11.         fast = fast->next;
12.     }
14.     while (fast != NULL) {
15.         slow = slow->next;
16.         fast = fast->next;
17.     }
19.     return slow;
20. }

复制代码

3. 快慢指针的优缺点

3.1 优点

• 高效：快慢指针可以在一次遍历中完成多种任务，时间复杂度通常为 O(n)。
  
• 轻便：代码实现轻便，易于明白和维护。
  
• 实用广泛：实用于多种链表题目，如探求中心节点、检测环、找到环的入口等。
  

3.2 缺点

• 界限条件复杂：必要过细处置处罚界限条件，如链表为空、链表长度为 1 等。
  
• 指针操纵复杂：指针操纵容易堕落，特别是在处置处罚环和界限条件时。
  

4. 总结

快慢指针是一种非常实用的链表题目办理本领，通过公道利用快慢指针，可以高效地办理多种链表题目。把握快慢指针的利用方法和常见应用场景，将有助于你在算法口试和现实开发中更好地应对链表相干题目。渴望本文对你的学习和工作有所资助。