【面试经典150 | 链表】循环链表

文章目录

Tag

【快慢指针】【哈希集合】【计数】【链表】

题目来源

141. 环形链表

题目解读

判断一个链表中是否存在环。

解题思路

链表中有环，那么在遍历链表中节点的时候就有部分元素被重复遍历，于是可以想到使用一个集合来记录已经遍历的节点，如果集合中有节点在遍历的时候第二次出现，那么一定存在环。该方法看似可以判断环的问题，但是链表中的节点会存在重复值，在无环的链表中也可能存在某些节点值被遍历了两次，导致无环链表被误判成有环链表。

如果集合中存放的是节点而不是节点的值呢？这样就可以唯一表示每一个节点了，因为每一个节点实际上是一个结构体（c语言中）或者类（c++中），都是以地址的形式存在于栈上。

接下来将介绍三种判断链表中是否有环的方法，方法一是哈希集合的方法，方法二是一种数学上的方法，方法三是一种 “巧妙” 的方法。这三种方法都推荐大家认真学习，务必要掌握。

方法一：哈希集合

遍历链表，将经过的节点存到哈希集合中，如果集合中已经存在了该节点，就说明链表中存在环。

实现代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        unordered_set<ListNode*> st;
        while (head) {
            if (st.count(head)) {
                return true;
            }
            st.insert(head);
            head = head->next;
        }
        return false;
    }
};

复杂度分析

时间复杂度： O ( N ) O(N) O(N)，其中 N N N 是链表中的节点数。最坏情况下我们需要遍历每个节点一次。

空间复杂度： O ( N ) O(N) O(N)，其中 N N N 是链表中的节点数。主要为哈希表的开销，最坏情况下我们需要将每个节点插入到哈希表中一次。

方法二：快慢指针

我们可以使用快慢指针来判断是否有环。定义一个慢指针 slow 每次只移动一个位置，定义一个快指针 fast 每次移动两个位置，两个指针从同一个节点出发：

  • 如果链表中没有环，快指针一定会到达最后的 nullptr 节点；
  • 如果链表中有环，那么两个指针一定会在环内相遇。

实现代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (head == nullptr || head->next == nullptr)
			return false;
		ListNode *slow = head;
		ListNode *fast = head->next;
		while (fast != slow) {
			if (fast == nullptr || fast->next == nullptr)
				return false;
			slow = slow->next;
			fast = fast->next->next;
		}
		return true;
    }
};

代码中的 while 循环的条件语句是 slow != fast，即快慢指针相等的时候才会退出循环。我们初始化的慢指针为 head，快指针为 head->next，如果我们将两个指针初始都置于 head，那么 while 循环就不会执行，才会对两指针进行上述的初始化，相当于快慢指针是从 dummy head（头结点的虚构的上一个）这个节点同时出发的，我们先让快慢指针出发了各自的一个步幅，这样就可以使用 while 循环了。

当然也可以使用 do...while 循环，这样的话快慢指针初始化为 head 就可以了。

while 语句与 do...while 语句的区别在于前者是先判断再执行，而后者是先执行再判断。

复杂度分析

时间复杂度： O ( N ) O(N) O(N)，其中 N N N 是链表中的节点数。

空间复杂度： O ( 1 ) O(1) O(1)。

方法三：计数

方法二就比较简单了。如果链表中存在环，那么在遍历链表的时候一定有一些节点值被重复遍历了多次。由于本题中链表最多有 1 e 4 1e4 1e4 个节点，因此我们边遍历节点边计数（从头结点到当前节点的个数），如果数量大于 1 e 4 1e4 1e4，那么链表中一定存在环，我们直接退出迭代遍历的过程，返回 false。

实现代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        int cnt = 0;
        while (head) {
            ++cnt;
            if (cnt > (int)1e4) {
                return true;
            }
            head = head->next;
        }
        return false;
    }
};

复杂度分析

时间复杂度： O ( N ) O(N) O(N)，其中 N N N 是链表中的节点数。我们只有遍历每个节点一次之后才能判断出有没有环。

空间复杂度： O ( 1 ) O(1) O(1)。

拓展

本题中如果还需要求有环链表中的入环点，那么该怎么解决呢？也就是 142. 环形链表 II 这个题目要解决的问题。

最简单的方法还是哈希集合的方法，当某个节点第二次出现，该节点就是要求的入环点，该方法很简答这里不予说明。

重点来看一下如何使用 快慢指针法 来求入环点。

先来假设一些变量，入环点之前的距离为 a，入环点到快慢指针第一相遇的点的距离为 b，此时环中剩下的距离为 c，快指针在环中走了 n n n 圈之后，快、慢指针第一次相遇，于是快慢指针行走的位置距离为：

  • 慢指针：a+b；
  • 快指针：a+b+n(b+c)。

慢指针每次走一个节点位置，快指针每次走两个节点位置，快指针走的路程就是慢指针的两倍，所以快慢指针行走的位置距离有这样的关系：

2 ( a + b ) = a + b + n ( b + c ) 2(a+b)=a+b+n(b+c) 2(a+b)=a+b+n(b+c)

化简得到：

c = a + b + ( b + c ) ( n − 1 ) c = a+b+(b+c)(n-1) c=a+b+(b+c)(n−1)

根据以上公式推导可以知道，当入环点到第一次相遇点的距离加上 n − 1 n-1 n−1 圈的环的长度等于链表头部到入环点的距离。进一步来讲，如果两个指针分别从头结点和第一次相遇点出发，每次行进一个节点，那么它们相遇的节点（第一次相遇）就是入环点。

实现代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (head == NULL || head->next == NULL || head->next->next == NULL) {
            return NULL;
        }

        ListNode *slow = head->next, *fast = head->next->next;
        while (slow != fast) {
            if (fast->next == NULL || fast->next->next == NULL) {
                return NULL;
            }
            slow = slow->next;
            fast = fast->next->next;
        }

        fast = head;
        while (slow != fast) {
            slow = slow->next;
            fast = fast->next;
        }
        return slow;
    }
};

其他语言

python3

以下是 快慢指针法 判断链表中是否有环的python3语言代码

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if not head or not head.next:
            return False
        
        slow = head
        fast = head.next
        while fast != slow:
            if not fast or not fast.next:
                return False
            slow = slow.next
            fast = fast.next.next
        return True

写在最后

如果文章内容有任何错误或者您对文章有任何疑问，欢迎私信博主或者在评论区指出 ???。

如果大家有更优的时间、空间复杂度方法，欢迎评论区交流。

最后，感谢您的阅读，如果感到有所收获的话可以给博主点一个 ? 哦。