程序员

142. Linked List Cycle II

2017-11-13  本文已影响0人  Nautilus1

题目描述:给一个链表,判断其中环的起始结点,若没有环则返回null。要求不改变链表,空间复杂度O(1)。

分析:这题与141题是同一个算法引出的一系列问题,即Floyd判圈算法,又称龟兔赛跑算法,可以在有限状态机、迭代函数或者链表上判断是否存在环,并求出该环的起点与长度的算法。

算法的核心思想是设置快慢指针,例如设fast指针的速度是slow指针的2倍,若两指针能相遇则说明有环,否则无环。

例如有环链表如下图:



算法可以解决的问题有:

  1. 判断链表中是否有环,即141题。
  1. 计算环的长度。
  1. 找到环中第一个节点,即Y点。
    根据结论a=c,让两个指针分别从X和Z开始走,每次走一步,则正好会在Y相遇,也就是环的第一个节点。

  2. 将有环的链表变成单链表(解除环)
    在上一个问题的最后,将c段中Y点之前的结点与Y的链接切断即可。

  3. 判断两个单链表是否有交点,并找到第一个相交的结点。

在slow指针入环后,在最多走一圈的时间内必将遇到fast,时间复杂度O(n),空间O(1)。

代码

/**
 * 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) {
        ListNode *slow = head, *fast = head;
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
            if ( slow == fast)           //找到相遇点
            {
                ListNode *p = head;
                while( p != slow)            //slow从Z点出发,新指针P从起点X出发同时走,直到相遇
                {
                    p = p->next;
                    slow = slow->next;
                }
                return p;
            }
        }
        return nullptr;
    }
};

参考:http://blog.csdn.net/sqiu_11/article/details/69841292

上一篇 下一篇

猜你喜欢

热点阅读