单链表之环形链表

程序员小熊

发布于 2021-05-28 13:54:58

7620

文章被收录于专栏：程序员小熊带你学算法程序员小熊带你学算法

不论在面试或者刷题过程中，很大概率都会遇到环形链表这种类型的题目，例如 leetcode 141. 环形链表以及 leetcode 142. 环形链表 II 等，本文主要介绍通过快慢指针法来解决此类题型，以供大家参考。

环形链表

环形链表大致样子如下图所示：

快慢指针法

判断链表是否是环形链表，一般通过快慢指针法。

操作步骤

一、分别定义两个均指向头节点的指针（fast/slow）；

二、快指针每次走两步，慢指针每次走一步；

三、如果链表存在环，则快慢指针一定会在环中相遇。

如下图示，快慢指针行走的轨迹如下：

faster： 1--->3--->5--->7

slower：1--->2--->3--->4

faster： 7--->5

slower：4--->5

当他们同时到达节点 5 时，完美相遇。

举栗1：判断链表是否有环

题目

Show me the Code

//  C 语言
bool hasCycle(struct ListNode *head) {
    /* 特判 */
    if (head == NULL || head->next == NULL) {
        return false;
    }
    struct ListNode *slow = head, *fast = head;
    /* fast指针走过链表末端，说明链表无环*/
    while((fast != NULL) && (fast->next != NULL)) {
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast) {
            return true;
        }
    }
    return false;
}

# python3
class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        if not head or not head.next: return False     
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next 
            if slow is fast: return True
        return False

举例2：求入环的第一个节点

题目

思路

本题除了需要判断链表是否有环外，如果有环还要求入环的第一个节点，因此是上一个题目的升级版本，还是以快慢指针中举例的那个链表作为示例，下图将描述当链表有环的时候，如何求出入环的第一个节点，见下图示：

已判断链表有环

求入环的第一个节点

让慢指针重新指向链表的头节点，并让快慢指针同时每次只走一步

faster：5--->6--->7

slower：1--->2--->3

继续走

faster：7--->4

slower：3--->4

当他们同时到达节点 4 时，再次完美相遇。

因此，由上面的图可知，当判断链表有环（快慢指针相遇）之后，再让快（或者慢）指针重新指向链表头节点，另外一个指针仍保持指向不变，然后让快/慢指针同时走，且每次只走一步，当他们再次相遇时，此时相遇的节点就是入环的第一个节点。

Show me the Code

//  c 语言
struct ListNode *detectCycle(struct ListNode *head) {
    /* 记录是否有环 */
    bool flag = false;  
    struct ListNode *slow = head, *fast = head;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        /* 有环则更新 flag 的值，并跳出循环寻找入环第一个节点 */
        if (slow == fast) {
            flag = true;
            break;
        }
    }
    /* 无环则直接返回空 */
    if (flag == false) {
        return NULL;
    }
    /* 慢指针重新指向链表头节点，快指针仍指向相遇节点 */
    slow = head;
    /* 快慢指针每次走一步，相遇节点即为入环第一个节点 */
    while (fast != slow) {
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}

//  go 语言

func detectCycle(head *ListNode) *ListNode {
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        fast, slow = fast.Next.Next, slow.Next
        if fast == slow {
            break
        }
    }
    if fast == nil || fast.Next == nil {
        return nil
    }
    slow = head
    for fast != slow {
        fast, slow = fast.Next, slow.Next
    }
    return fast
}