力扣学习笔记:142. 环形链表 II

  • 时间:
  • 浏览:
  • 来源:互联网

题目:142.环形链表II
建议:先看环形链表Ⅰ

算法
哈希表

  • 和 Ⅰ类似,只是在碰到前面遇到过的结点,就返回该结点的地址即可

快慢指针

  • 我们将入环结点之前的结点距离设为 a ,将在环上快慢指针相遇的结点逆时针到入环结点的距离设为 b ,将在环上快慢指针相遇的结点顺时针到入环结点的距离设为 c 。
  • 我们可以计算 a + n * c + (n + 1) * b = 2 * ( a + b) (快指针的速度是慢指针的两倍)
  • 化简得 a = c + (n - 1) * ( b + c)
  • 这样子,我们知道,a 等于 c 加上 (n - 1)圈
  • 我们可以设一个ptr指针指到起点,让它和慢指针一起出发,最终会在入环结点碰头,返回地址即可

源代码

/**
 * 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 == nullptr){
            return nullptr;
        }
        ListNode* fast;
        ListNode* low;
        ListNode* ptr;

        fast = head;
        low = head;
        ptr = head;

        while(fast != nullptr && fast->next != nullptr && low != nullptr){
            fast = fast->next->next;
            low = low->next;
            if(fast == low){
                while(ptr != low){
                    ptr = ptr->next;
                    low = low->next;
                }
                return ptr;
            }
        }
        return nullptr;
    }
};

本文链接http://element-ui.cn/article/show-218963.aspx