当前位置：首页 > article >正文

【快慢指针】突破环形链表

article 2024/11/13 11:07:41

🚀个人主页：一颗小谷粒

🚀所属专栏：力扣刷题

很荣幸您能阅读我的文章，诚请评论指点，欢迎欢迎 ~

一、链表的中间结点

1.1 题目要求

1.2 图解分析

1.3 Java代码实现

1.4 复杂度分析

二、环形链表 I

2.1 题目要求

2.2 算法分析

2.3 Java代码实现

2.4 复杂度分析

三. 环形链表 II

3.1 题目要求

3.2 图解分析

3.3 Java代码实现

3.4 复杂度分析

四、总结

一、链表的中间结点

首先，让我们通过一道找链表的中间结点的题目来认识一下什么是快慢指针，以及它在题中是如何运用的！

1.1 题目要求

leetcode876.链表的中间结点这道题就可以使用快慢指针来解答，题目如下：

876. 链表的中间结点 - 力扣（LeetCode）

1.2 图解分析

我们用两个指针指向链表的头结点，一个叫快指针(fast)，一个叫慢指针(slow)，每次循环慢指针走一步，快指针走两步。

若链表长度为3 ，一次循环后结束，如图：

若链表长度为5 ，两次循环后结束，如图：

链表长度为奇数的时候，若快指针在最后一个节点，那么慢指针一定在中间节点

那么链表长度为偶数呢？

以链表长度为2举例，一次循环后结束，如图：

若链表长度为4 ，两次循环后结束，如图：

对于偶数节点，如果快指针指向空，那么慢指针一定在中间节点上

综合两种情况，当快指针指向空，或者它的下一个节点指向空，这个时候就退出循环

1.3 Java代码实现

    public ListNode middleNode(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

1.4 复杂度分析

当快指针走到链表末尾的时候循环就结束了，所以时间复杂度是O(n)的。
空间复杂度由于我们只用到若个额外变量，所以它是O(1)的。

OK！通过这道题相信大家对快慢指针已经有了一个基本的认识了~~

二、环形链表 I

2.1 题目要求

leetcode.141 题目如下：

141. 环形链表 - 力扣（LeetCode）

2.2 算法分析

慢指针每次循环走一步，如果图中有环的话，那么慢指针一定会进入到环中，由于快指针相对于慢指针每次循环多走了一步，所以快指针肯定会与慢指针相遇。

所以我们只需要在第一题代码每次循环时判断快慢指针是否会相遇即可！如果链表成环，快慢指针一定会相遇！

2.3 Java代码实现

    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if(slow==fast){
                return true;
            }
        }
        return false;
    }

2.4 复杂度分析

由于慢指针进入环后，我们的循环次数是小于环的长度的，所以时间复杂度是O(n)的。
空间复杂度是O(1)的，因为我们只用到若个额外变量。

三. 环形链表 II

3.1 题目要求

leetcode.142 题目如下：

142. 环形链表 II - 力扣（LeetCode）

这个题与141相比，不仅要判断是否有环，还要找到环的入口！

3.2 图解分析

如图所示：

环长 = b + c
慢指针移动距离 = a + b
快指针移动距离 = a + k(b+c) + b

由于快指针移动距离是慢指针的两倍，所以推导得：

那么 a - c = (k - 1)(b +c) 意味着什么呢？

slow 从相遇点出发，head从头节点出发，走c步后，slow在入口，head 到入口的距离也恰好是环长的倍数，继续走，两者必然会在入口相遇！

这里有个结论：当快慢指针相遇时，慢指针还没有走完一整圈

大家可以在本子上画图来一步步模拟这个过程，相信你会理解的！

3.3 Java代码实现

    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if(slow==fast){
                while(slow!=head){
                    slow = slow.next;
                    head = head.next;       
                }
                return slow;
            }
        }
        return null;
    }