Huge Lemon的博客

环路检测

2020-02-29

LeetCode 面试题 02.08. Linked List Cycle LCCI

题目描述

给定一个有环链表，实现一个算法返回环路的开头节点。
有环链表的定义：在链表中某个节点的next元素指向在它前面出现过的节点，则表明该链表存在环路。

示例 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
解释：链表中没有环。

解题思路

经典的快慢指针问题，这里给出C的解法。

  1. 设置快慢指针
  2. 找到第一次相遇【快慢指针相遇】
  3. 再出发慢指针【从头结点出发的慢指针与快指针】
  4. 相遇即所求

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode *slow = head, *fast = head;
    // 快慢指针
    while (fast != NULL && fast->next != NULL){
        slow = slow->next;
        fast = fast->next->next;
        // 如果相遇了就break
        if (slow == fast) break;
    }
    // fast到了链表尾部,说明链表无环
    if (fast == NULL || fast->next == NULL) return NULL;
    // 慢指针从头开始, 快慢指针再一次相遇就是在环的起点
    slow = head;
    while (slow != fast){
        slow = slow->next;
        fast = fast->next;
    }
    return fast;
}
Tags: 算法 LeetCode
← 重排链表 二进制链表转整数 →
赏
使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助，欢迎点击上方按钮对我打赏