142.Linked List Cycle II

Tags: Medium Linked List

Links: https://leetcode.com/problems/linked-list-cycle-ii/

---

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.

Example 2:

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.

Example 3:

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

Follow-up: Can you solve it without using extra space?

---

/**
 * 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) return head;

        ListNode * slow = head, *fast = head;
        while (fast && fast -> next) {
            slow = slow -> next;
            fast = fast -> next -> next;
            if (slow == fast) break;
        }
        if (!fast || !fast -> next) return nullptr;

        slow = head;
        while (slow != fast) {
            slow = slow -> next;
            fast = fast -> next;
        }

        return slow;
    }
};

---

在程序20行容易出错，最开始漏写了，因为如果链表中没有环，那么就是由于fast访问到了链表的尾端，此时就应该返回了。

设从头节点到环的起点距离为$a$，环的起点到第一次相遇的节点之间的距离为$b$，第一次相遇节点到尾端距离为$c$，显然$b+c$为环一圈的周长。第一次相遇时，快指针走过的距离：$a+b+c+b$，慢指针走过的距离是$a+b$，因为快指针速度是慢指针的两倍，所以$a+b+c+b = 2(a+b)$，则可知$a=c$，

所以思路是如果存在环，那么第一次相遇后，其中一个指针回到起始节点，另一个指针继续走，两个指针每次移动的距离都是1，那么第二次相遇的时候走过的距离就都是$c$了，所以返回这个节点即可。

有环单链表，如何破环

这个思路继承自上面寻找环的入口，只需要改动在第一次相遇后的程序：

class Solution {
public:
    void breakCycle(ListNode *head) {
        ListNode * slow = head, *fast = head;
        while (slow != fast) {
            slow = slow -> next;
            fast = fast -> next -> next;
        }

        slow = head;
        while (slow -> next != fast -> next) {
            slow = slow -> next;
            fast = fast -> next;
        }
        fast -> next = nullptr;
    }
};

计算单链表中环的长度

思路和上面是一样的，只不过多了个计数器，计数器始终绑定在慢指针上，每走一步就+1，两个指针第一次相遇慢指针走过的步数就是环的长度。因为环的长度是$b+c$，慢指针走过的是$a+b$，因为$a=c$，所以可得。如果无环则返回-1.

class Solution {
public:
    int cycleLength(ListNode *head){
        if (!head) return -1;
        int cnt = 0;
        ListNode * dummy = new ListNode(0);
        dummy -> next = head;
        ListNode *slow = dummy, *fast = dummy;
        while (fast -> next && fast -> next -> next) {
            slow = slow -> next;
            fast = fast -> next -> next;
            ++cnt;
            if (slow == fast) break;
        }
        if (!fast -> next || !fast -> next -> next) return -1;

        return cnt;
    }
};

无环单链表的中间节点

一个无环单链表，返回链表的中间节点，如果长度为偶数，返回两个节点的任意一个。

仍然是快慢指针思路，快指针走两步，慢指针走一步，那么快指针走到末尾，慢指针刚好走到一半。

class Solution {
public:
    ListNode *middleNode(ListNode *head){
        if (!head) return nullptr;

        ListNode *slow = head, *fast = head;
        while (fast -> next && fast -> next -> next) {
            slow = slow -> next;
            fast = fast -> next -> next;
        }

        return slow;
    }
};

这个方法的用处在LeetCode 143.Reorder List体现出来。

判断两个单链表是否相交

首先假设两个单链表都无环，相交情况如下图：

有两种思路：

一种是根据上面题目很自然想到的：先遍历第一个链表，由于无环，肯定可以访问到最后，然后把最后节点和自己的头节点连起来形成一个环，然后去访问第二个链表，如果两个链表相交，那么第二个链表就会形成环，否则不会，所以转化成了链表找环的问题，如果想输出交点思路同上。

第二种方法较第一种实施起来更为简单，因为第一种还需要去改动链表，最后记得破环恢复原状。不妨换一种思路，如果两个链表相交，那么一定有公共节点，在哪个位置不清楚，但是可以知道相交的链表最后一个节点一定是公共节点。那么访问第一个链表，记录最后一个节点，再访问第二个节点，如果第二个链表访问到最后也没有找到与记录节点相同的节点，那么没有相交，否则相交。

这里实现第二种方案：

class Solution {
public:
    bool isIntersected(ListNode *head1, ListNode * head2){
        if (!head1 || !head2) return false;

        ListNode * prob1 = head1;
        while (prob1 -> next)
            prob1 = prob1 -> next;
        ListNode * prob2 = head2;
        while (prob2 -> next)
            prob2 = prob2 -> next;

        if (prob1 == prob2) return true;

        return false;
    }
};

两个无环单链表找交点

一种思路是先遍历第一个链表，由于无环，肯定可以访问到最后，然后把最后节点和自己的头节点连起来形成一个环，然后去访问第二个链表，第二个链表就会形成环，问题转化成了一个单链表找环入口点问题，和LeeCode 142就是一个问题了。

第二种思路是由于无环，两个链表从头开始访问一定可以到尾端。首先判断是否相交，相交的情况我们采用一个计数器记录走过的长度，假设短链为链1，长链为链2，设公共长度为$l$，则链1的长度$s1=l1 + l$，链2的长度$s2 = l2+l$，差值为$l2-l1$，那么从头开始访问，让长链先走$l2-l1$步，然后两个链的指针同时移动，那么第一次相交就是交点。

class Solution {
public:
    bool isIntersected(ListNode *head1, ListNode * head2){
        if (!head1 || !head2) return false;

        ListNode * prob1 = head1;
        while (prob1 -> next)
            prob1 = prob1 -> next;
        ListNode * prob2 = head2;
        while (prob2 -> next)
            prob2 = prob2 -> next;

        if (prob1 == prob2) return true;

        return false;
    }

    ListNode * findIntersected(ListNode *head1, ListNode * head2){
        if (!isIntersected(head1, head2)) return nullptr;

        int s1 = 1, s2 = 1; //如果为0则比真实长度少1，也不影响差值计算结果
        ListNode * prob1 = head1; 
        while (prob1 -> next){
            prob1 = prob1 -> next;
            ++s1;
        }
        ListNode * prob2 = head2;
        while (prob2 -> next){
            prob2 = prob2 -> next;
            ++s2;
        }

        int delta = 0;
        bool flag = true; //记录哪个链是长链
        if (s1 > s2){
            delta = s1 - s2;
        } 
        else{
            delta = s2 - s1;
            flag = false;
        } 

        prob1 = head1;
        prob2 = head2;
        if (flag){ //链1较长
            s1 = 0;
            while (s1 != delta){
                prob1 = prob1 -> next;
                ++s1;
            }
            while (prob1 != prob2){
                prob1 = prob1 -> next;
                prob2 = prob2 -> next;
            }
            return prob1;
        }

        s2 = 0;
        while (s2 != delta){
            prob2 = prob2 -> next;
            ++s2;
        } 
        while (prob1 != prob2){
            prob1 = prob1 -> next;
            prob2 = prob2 -> next;
        }
        return prob1;
    }
};

如果两个单链表可能有环，如何判断链表是否相交

两个单链表可能有环，可分为4类（两个链表标记为链1和链2）：

• 链1有环，链2有环
• 链1有环，链2无环
• 链1无环，链2有环
• 链1无环，链2无环

最简单的情况是两个链中一个有环，一个无环，这种情况下必然无交点。

两个无环的链表思路和“判断无环链表是否相交一样了”，判断尾指针即可。

两个单链表有环不相交，显然环不会有重合的部分。两个链都有环且相交，分为两种情形如下图，但是一个共同点是，环是两个单链表的公共部分。

很明显，区别在于环的入口不同。所以思路是：

• 先写一个判断单链表是否有环的程序，分别判断两个单链表是否有环。
• 一个有环，一个无环，则不相交。
• 两个无环，那么应用判断尾节点的方法。
• 两个都有环，预先得到两个环的入口节点和环的长度（记为$s$），如果环的长度不一致，则不相交。如果环的长度一致，考虑入口节点是否相同，如果相同，那么则相交。如果入口节点不同，设置一个慢指针在第一个入口，一个快指针（每次走两步）在第二个入口，两个指针如果在同一个环里面且入口点不同，相遇时慢指针最多走$s/2$步。所以可以增加一个计数器，如果慢指针走了$s/2$步还是没有和快指针相遇，那么就是属于不同的环，否则就相交。

class Solution {
public:
    //计算单链表环的长度
    int cycleLength(ListNode *head){ 
        if (!head) return -1;
        int cnt = 0;
        ListNode * dummy = new ListNode(0);
        dummy -> next = head;
        ListNode *slow = dummy, *fast = dummy;
        while (fast -> next && fast -> next -> next) {
            slow = slow -> next;
            fast = fast -> next -> next;
            ++cnt;
            if (slow == fast) break;
        }
        if (!fast -> next || !fast -> next -> next) return -1;

        return cnt;
    }

    //判断单链表是否有环，并返回环的入口节点
    ListNode *detectCycle(ListNode *head) {
        if (!head) return head;

        ListNode * slow = head, *fast = head;
        while (fast && fast -> next) {
            slow = slow -> next;
            fast = fast -> next -> next;
            if (slow == fast) break;
        }
        if (!fast || !fast -> next) return nullptr;

        slow = head;
        while (slow !=fast) {
            slow = slow -> next;
            fast = fast -> next;
        }

        return slow;
    }

    //判断两个无环单链表是否有交点
    bool isIntersected(ListNode *head1, ListNode * head2){
        if (!head1 || !head2) return false;

        ListNode * prob1 = head1;
        while (prob1 -> next)
            prob1 = prob1 -> next;
        ListNode * prob2 = head2;
        while (prob2 -> next)
            prob2 = prob2 -> next;

        if (prob1 == prob2) return true;

        return false;
    }

    //判断两个有环单链表是否有交点
    bool isCycleListIntersected(ListNode *head1, ListNode * head2){
        if (!head1 || !head2) return false;

        //得到两个单链表的环的长度和环入口节点
        ListNode * enterPoint1 = detectCycle(head1), * enterPoint2 = detectCycle(head2);
        int perimeter1 = cycleLength(head1), perimeter2 = cycleLength(head2);

        //一个有环，一个无环必不相交
        if ( (!enterPoint1 && enterPoint2) || (enterPoint1 && !enterPoint2) ) return false;

        //两个无环，尾节点判断法
        if (perimeter1 < 0 && perimeter2 < 0) return isIntersected(head1, head2);

        //两个都有环，先判断环的长度是否一致
        if (perimeter1 != perimeter2) return false;

        //判断入口节点是否相同，相同则相交
        if (enterPoint1 == enterPoint2) return true;

        //环长度相同但是入口节点不同
        int cnt = 0; 
        ListNode * slow = enterPoint1, *fast = enterPoint2;
        while (cnt != perimeter1 / 2 + 1){
            slow = slow -> next;
            fast = fast -> next -> next;
            if (slow == fast) return true;
        }

        return false;
    }
};