NC3 链表中环的入口节点 牛客

描述

对于一个给定的链表，返回环的入口节点，如果没有环，返回null

拓展：

你能给出不利用额外空间的解法么？

 

 

题解：

快指针与慢指针均从X出发，在Z相遇。此时，慢指针行使距离为a+b，快指针为a+b+n(b+c）。

所以2*(a+b)=a+b+n*(b+c),推出

a=(n-1)*b+n*c=(n-1)(b+c)+c;

得到，将此时两指针分别放在起始位置和相遇位置，并以相同速度前进，当一个指针走完距离a时，另一个指针恰好走出 绕环n-1圈加上c的距离。

 

 题源：https://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4?tpId=188&&tqId=38577&rp=1&ru=/activity/oj&qru=/ta/job-code-high-week/question-ranking

python：

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

#
# 
# @param head ListNode类 
# @return ListNode类
#
class Solution:
    def detectCycle(self , head ):
        # write code here
        s1=head
        s2=head
        if head==None:
            return None
        
        while(1):
            s1=s1.next
            if s1==None:
                return None
            if s2.next!=None and s2.next.next!=None:
                s2=s2.next.next
            else:
                return None
            if(s1==s2):
                s1=head
                while(s1!=s2):
                    s1=s1.next
                    s2=s2.next
                return s1                    

c++:

/**
 * 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==NULL) return NULL;
        ListNode *a=head;
        ListNode *a2=head;
        while(1)
       {
           if (a->next!=NULL) a=a->next;
              else return NULL;
           if (a2->next!=NULL && a2->next->next!=NULL) a2=a2->next->next;
              else return NULL;
           if (a==a2) break;
      }
       a=head;
       while(1)
       {
           if (a==a2) return a;
           a=a->next;
           a2=a2->next;
           
       }
    }
};