• 【面试经典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;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    复杂度分析

    时间复杂度: 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;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24

    代码中的 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;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    复杂度分析

    时间复杂度: 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)(n1)

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

    实现代码

    /**
     * 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;
        }
    };
    
    • 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
    • 28
    • 29
    • 30
    • 31
    • 32

    其他语言

    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
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    写在最后

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

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

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

  • 相关阅读:
    Maven 自动化构建
    App移动端测试(1)—— Android sdk部署
    一文搞懂CAN总线协议
    【MySQL数据库笔记 - 进阶篇】(一)存储引擎
    【Linux系统编程】进程控制
    学习Rust第14天:HashMaps
    SpringCloud基础8——多级缓存
    英特尔:如何从“小芯片”布局到通用量子计算机
    Linux ./configure sudo make && make install
    SSL加密
  • 原文地址:https://blog.csdn.net/weixin_54383080/article/details/133993161