142.Ring linkedII

2024-01-01

字数统计: 738字 | 阅读时长: 3min

2023-07-01 (1).png
142.Ring listII.md

Thought：

Problem -solving：

这类Linkedtopic一般都yes使用双pointer法解决的，For example, looking for distance tail K Node、Find a ring entrance、Find the entrance of the public tail, etc.。

Algorithm：

Double pointer met for the first time： Set two pointers fast，slow 指向Linked头部 head，fast Walk per round 2 step，slow Walk per round 1 step；

a. First result： fast pointer走过Linked末端，说明Linked无环，直接return null；

.TIPS: If there is a ring，Two pointers will definitely meet。Because every time I go 1 wheel，fast and slow Pitch +1，fast The event will catch up slow；
b. Second result： whenfast == slowhour， Two pointers in the ring First encounter 。下面分析此hourfast and slowPassing step数关系：

.设Linked共have a+b Node，in Linked头部到Linked入口 have a Node（不计Linked入口节点）， Linked环 have b Node（这里需要Notice，a and b yes未知数，例如图解上Linked a=4 , b=5）；Set two pointers分别走了 f，s step，则have：
a. fast 走的step数yesslowstep数的 2 Double，Right now f=2s；（Analyze： fast Walk per round 2 step）
b.fast Compare slowGo more n Length of a ring，Right now f=s+nb；（ Analyze： Double pointers have gone through a step，然后在环Inside绕圈直到重合，重合hour fast Compare slow Go 环的长度整数Double ）；
.The above two types are reduced：f=2nb，s=nb，Right nowfastandslow The pointer left separately 2n，n indivual Circumference of the ring （Notice： n yes未知数，不同Linked的情况不同）。

Current situation analysis：

.if让pointer从Linked头部一直向前走并统计step数k，那么所have 走到Linked入口节点hour的step数 yes：k=a+nb（Leave first a step到入口节点，Over time 1 Ring（ b step）I will go to the entrance node again）。

..Current，slow pointerPassingstep数为 nb step。therefore，We just find a way slow Go again a step停下来，You can get to the entrance to the ring。

…但yes我们不知道 a Value，what to do？依然yes使用双pointer法。我们构建一indivualpointer，此pointer需要have以下性质：此pointerandslow Go forward together a step后，The two nodes at the entrance re -coincide。So where does it need to get to the entrance node? a step？答案yesLinked头部head。
Double pointer met for the second time：
.slowpointer Unchanged position ，Willfastpointer重新指向Linked头部节点；slowandfast同hour每wheel向前走 1 step；

..TIPS：此hour f=0，s=nb ；
…when fast pointer走到f=a stephour，slow pointer走到steps=a+nb，此hour 两pointer重合，并同hour指向Linked环入口。
returnslowpointer指向的节点。

Complexity analysis：

hour间复杂度 O(N) ：In the second encounter，慢pointer须走step数 a<a+b；First encounter中，慢pointer须走step数 a+b−x<a+b，in x 为双pointer重合点and环入口距离；therefore总体为线性复杂度；
Spatial complexity O(1) ：双pointer使用常数大小的额外空间。

Code：

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        a = head
        b = head
        while True:
            if not b or not b.next:
                return None
            a = a.next
            b = b.next.next
            if b == a:
                break
        b = head
        while a != b:
            a, b = a.next, b.next
        return b

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *a = head;
        ListNode *b = head;
        while (true) {
            if (!b or !b->next) {
                return nullptr;
            }
            a = a->next;
            b = b->next->next;
            //becauseb每次走两step，soabMust meet
            if (a == b) {
                break;
            }
        }
        // After meetingaWait in placeb, b去Linked头部
        b = head;
        while(a!=b){
            a = a->next;
            b = b->next;
        }

        return a;
    }
};