Leetcode日记：141&142.链表中的环

141题目：判断是否存在环

Given a linked list, determine if it has a cycle in it.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Example 1:

1
2
3
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.

!(leetcode141-1.png)

Example 2:

1
2
3
Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the first node.

!(leetcode141-2.png)

Example 3:

1
2
3
Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

!(leetcode141-3.png)

141问题分析

这道题意思很简单，判断输入的链表是否存在环。
上次刚讲到快慢指针的应用问题，这次就遇到了链表中的环。那么如何将二者结合起来呢？

其实答案很简单，快指针一下走两步，慢指针一下走一步，如果链表存在环，那么快慢指针一定会在环的某个位置相遇。

141代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean hasCycle(ListNode head) {
    ListNode slow = new ListNode(0);
    ListNode fast = new ListNode(0);
    slow.next = head;
    fast.next = head;
    if(head==null)
        return false;
    while(fast!=null&&fast.next!=null){
        //如果快慢指针相遇，说明存在环
        if(slow==fast)
            return true;
        slow = slow.next;
        fast = fast.next.next;
    }
    return false;
}

142题目：找出链表中环的起始位置

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Note: Do not modify the linked list.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.

!(leetcode141-1.png)
Example 2:

1
2
3
Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.

!(leetcode141-2.png)
Example 3:

1
2
3
Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.

!(leetcode141-3.png)

142题目分析

这道题在141的基础上多了一个找出环的初始位置，这个需要用到一个常识或者说小技巧，我们要知道。
快慢指针相遇的位置和环起点的位置，以及链表头节点位置关系：

第一次碰撞点Pos到连接点Join的距离=头指针到连接点Join的距离，因此，分别从第一次碰撞点 Pos、头指针 head 开始走，相遇的那个点就是连接点。

circle
circle

在环上相遇后，记录第一次相遇点为 Pos，连接点为 Join，假设头结点到连接点的长度为LenA，连接点到第一次相遇点的长度为x，环长为 R。
第一次相遇时，slow 走的长度 S = LenA + x;
第一次相遇时，fast 走的长度 2S = LenA + n*R + x;
所以可以知道，LenA + x = n*R;　　LenA = n*R -x;

142代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public ListNode detectCycle(ListNode head) {
                ListNode slow = head;
                ListNode fast = head;
    while (fast!=null && fast.next!=null){
        fast = fast.next.next;
        slow = slow.next;
        //相遇之后，从头节点出发
        if (fast == slow){
            ListNode slow2 = head;
            while (slow2 != slow){
                slow = slow.next;
                slow2 = slow2.next;
            }
            return slow;
        }
    }
    return null;
}

补充：求有环单链表的环长

在环上相遇后，记录第一次相遇点为Pos，之后指针slow继续每次走1步，fast每次走2步。在下次相遇的时候fast比slow正好又多走了一圈，也就是多走的距离等于环长。

circle
circle

设从第一次相遇到第二次相遇，设slow走了len步，则fast走了 2*len 步，相遇时多走了一圈：环长 = 2*len-len。

更多关于链表的问题

更多关于链表的问题请转到链表标签