Linked List - Linked List Cycle

优质

小牛编辑

133浏览

2023-12-01

Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?

这道题就是判断一个链表是否存在环，非常简单的一道题目，我们使用两个指针，一个每次走两步，一个每次走一步，如果一段时间之后这两个指针能重合，那么铁定存在环了。

代码如下：

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head == NULL || head->next == NULL) {
            return false;
        }
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast->next != NULL && fast->next->next != NULL) {
            fast = fast->next->next;
            slow = slow->next;
            if(slow == fast) {
                return true;
            }
        }
        return false;
    }
};

Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Follow up:
Can you solve it without using extra space?

紧跟着第一题，这题不光要求出是否有环，而且还需要得到这个环开始的节点。譬如下面这个，起点就是n2。

        n6-----------n5
        |            |
  n1--- n2---n3--- n4|

我们仍然可以使用两个指针fast和slow，fast走两步，slow走一步，判断是否有环，当有环重合之后，譬如上面在n5重合了，那么如何得到n2呢？

首先我们知道，fast每次比slow多走一步，所以重合的时候，fast移动的距离是slot的两倍，我们假设n1到n2距离为a，n2到n5距离为b，n5到n2距离为c，fast走动距离为a + b + c + b，而slow为a + b，有方程a + b + c + b = 2 x (a + b)，可以知道a = c，所以我们只需要在重合之后，一个指针从n1，而另一个指针从n5，都每次走一步，那么就可以在n2重合了。

代码如下：

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
         if(head == NULL || head->next == NULL) {
            return NULL;
        }
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast->next != NULL && fast->next->next != NULL) {
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow) {
                slow = head;
                while(slow != fast) {
                    fast = fast->next;
                    slow = slow->next;
                }
                return slow;
            }
        }
        return NULL;
    }
};

Intersection of Two Linked Lists

Write a program to find the node at which the intersection of two singly linked lists begins.
For example, the following two linked lists:
A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗
B:     b1 → b2 → b3
begin to intersect at node c1.
Notes:
If the two linked lists have no intersection at all, return null.
The linked lists must retain their original structure after the function returns.
You may assume there are no cycles anywhere in the entire linked structure.
Your code should preferably run in O(n) time and use only O(1) memory.

这题需要得到两个链表的交接点，也就是c1，这一题也很简单。

遍历A，到结尾之后，将A最后的节点连接到B的开头，也就是c3 -> b1
使用两个指针fast和slow，从a1开始，判断是否有环
如果没环，在返回之前记得将c3 -> b1给断开
如果有环，则按照第二题的解法得到c1，然后断开c3 -> b1

代码如下：

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
               if(!headA) {
            return NULL;
        } else if (!headB) {
            return NULL;
        }
        ListNode* p = headA;
        while(p->next) {
            p = p->next;
        }
        //将两个链表串起来
        p->next = headB;
        ListNode* tail = p;
        p = headA;
        //fast和slow，判断是否有环
        headB = headA;
        while(headB->next && headB->next->next) {
            headA = headA->next;
            headB = headB->next->next;
            if(headA == headB) {
                break;
            }
        }
        if(!headA->next || !headB->next || !headB->next->next) {
            //没环，断开两个链表
            tail->next = NULL;
            return NULL;
        }
        //有环，得到环的起点
        headA = p;
        while(headA != headB) {
            headA = headA->next;
            headB = headB->next;
        }
        //断开两个链表
        tail->next = NULL;
        return headA;
    }
};