链表中环的入口结点

1、题目

image-20231009223317010

2、解题思路

思路：双指针

一快一慢指针。快指针每次跑两个element，慢指针每次跑一个。如果存在一个圈，经过一段时间后，快指针是能追上慢指针的。

如图所示，假设链表头到环入口结点X的距离为A，两指针相遇的结点为Y，X到Y的距离为B，Y到X的距离为C。设快指针进入环后经过n圈与慢指针相遇，根据假设可得到等式：\(2(A+B)=A+nB+(n-1)C\)。

image-20231009224631071

import java.util.*;

 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}

public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        
        if(pHead == null || pHead.next == null){
            return null;
        }

        ListNode fast=pHead;
        ListNode slow=pHead;

        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;

            if(fast==slow){
                ListNode slow2 = pHead;
                while(slow2 != slow){
                    slow = slow.next;
                    slow2 = slow2.next;
                }
                return slow2;
            }
        }

        return null;
    }
}

#自己写的幽默代码
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        
        
        a=head
        b=head

        while True:

            if a.next.next ==None:
                return None
            
            a = a.next.next
            b=b.next
            if a==b:
                c=head
                while c!=b:
                    c=c.next
                    b=b.next
                return c
        return None

#题解
class Solution(object):
    def detectCycle(self, head):
        fast, slow = head, head
        while True:
            if not (fast and fast.next): return
            fast, slow = fast.next.next, slow.next
            if fast == slow: break
        fast = head
        while fast != slow:
            fast, slow = fast.next, slow.next
        return fast