【LeetCode】【C++】Linked list cycle 2

1715 ワード

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?
この問題は難しくありませんが、extra spaceで作らなくても頭を働かせなければならないと思います.私は前に似たようなアルゴリズムの問題を見たことがあるので、すぐに思いつきました.
方法は,2つのポインタを用いて最初からポインタp 1を1回1歩,ポインタp 2を1回2歩,ループがあれば必ず2つのポインタが再会する場合である(Linked List Cycleで用いた).
次に,ループの開始ノードをどのように求めるかである.
このように,チェーンの始点からリングの始点までの距離をaと呼ぶと仮定できる.リングの長さをcと呼び,最初の出会い位置からリングの起点距離をpとする.まずp 1がp 2に追いつかれたときには必ずループ全体(なぜかというと?)つまり02 a+2 p=a+p+ncなので、a+p=ncがあります.現在、両ポインタはいずれもリングの起点がpを超えた位置にあり、さらにa距離を歩くとリングの起点に戻ることができる.aはちょうどチェーンの起点からリングの起点までの距離なので、私たちのもう一つのポインタはチェーンの起点に戻って、もう一つのポインタはまだその場にいて、同時に速度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 *p1=head;
        ListNode *p2=head;
        
        bool hasCycle = false;
        if (!head) return NULL;
        while(p2->next!=NULL){
            p1 = p1->next;
            p2 = p2->next->next;
            if (p2 == NULL) return NULL;
            if (p1 == p2){
                hasCircle = true;
                break;
            }
        }
        if (!hasCycle) return NULL;
        else{
            p2 = head;
            while (p1!=p2){
                p1 = p1->next;
                p2 = p2->next;
            }
            return p1;
        }
        
    }
};

新型コロナウイルス感染症（COVID-19）のオープンデータをPostgreSQLに格納する作業メモ

バブルソートのC++実装およびランダム配列の生成方法