142.环形链表II

142. 环形链表 II

给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。

说明：不允许修改给定的链表。

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

进阶：你是否可以不用额外空间解决此题？

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/linked-list-cycle-ii 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

同141题一样，这道题采用快慢指针方法解决，不同之处在于，本题需要找出相交的节点.

Floyd算法

想法

当然一个跑得快的人和一个跑得慢的人在一个圆形的赛道上赛跑，会发生什么？在某一个时刻，跑得快的人一定会从后面赶上跑得慢的人。

算法

Floyd 的算法被划分成两个不同的阶段。

在第一阶段，找出列表中是否有环，如果没有环，可以直接返回 null 并退出。否则，用相遇节点来找到环的入口。
如果有环slow == fast时，break；代表有环，进入第二阶段
在第二节点，将slow指针指向head， slow和fast都依次走一步。当slow 和 fast相等时，就是相交节点.

看图更容易理解一些：

WechatIMG250

代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


public static ListNode detectCycle(ListNode head) {

  			if(head == null || head.next == null) return null;

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

时间复杂度 : O(N)

空间复杂度 : O(1)

Contents

142. 环形链表 II

题解：

Floyd算法