LinkList9

发表于 更新于 分类于 ，

题目描述[原题链接][https://leetcode-cn.com/problems/linked-list-cycle-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
解释：链表中没有环。

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

算法描述

​ 这里我们初始化两个指针 - 快指针和慢指针。我们每次移动慢指针一步、快指针两步，直到快指针无法继续往前移动。如果在某次移动后，快慢指针指向了同一个节点，我们就返回它。否则，我们继续，直到 while 循环终止且没有返回任何节点，这种情况说明没有成环，我们返回 null ;

​ 给定之前找到的相遇点，此时将找到环的入口。首先我们初始化额外的两个指针： ptr1指向链表的头， ptr2指向相遇点。然后，我们每次将它们往前移动一步，直到它们相遇，它们相遇的点就是环的入口，返回这个节点。

C++代码

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
33
34
class Solution {
public:
    ListNode *get(ListNode* head){
        ListNode* tortoise = head;
        ListNode* hare = head;
        
        while(hare!=NULL&&hare->next!=NULL){
            tortoise = tortoise->next;
            hare = hare->next->next;
            if(tortoise==hare){
                return tortoise;
            }
        }
        return NULL;
    }
    ListNode *detectCycle(ListNode *head) {
        if(head==NULL)return head;
        
        ListNode* in = get(head);
        if(in==NULL){
            return NULL;
        }
        
        ListNode* ptr1 = head;
        ListNode* ptr2 = in;
        while(ptr1!=ptr2){
            ptr1=ptr1->next;
            ptr2=ptr2->next;
        }
        
        return ptr1;
        
    }
};

Java代码

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
public class Solution {
    ListNode get(ListNode head){
        ListNode tortoise = head;
        ListNode hare = head;
        while(hare != null&&hare.next!=null){
            tortoise = tortoise.next;
            hare = hare.next.next;
            if(tortoise == hare){
                return tortoise;
            }
        }
        return null;
    }
    public ListNode detectCycle(ListNode head) {
        if(head == null)return head;
        ListNode in = get(head);
        if(in == null)return null;
        ListNode ptr1 = head;
        ListNode ptr2 = in;
        while(ptr1!=ptr2){
            ptr1 = ptr1.next;
            ptr2 = ptr2.next;
        }
        return ptr1;
    }
}