【剑指Offer】（链表）链表中环的入口结点

深藏阁楼爱情的钟 2022-03-17 14:24 202阅读 0赞

**题目链接**：[https://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4?tpId=13&tqId=11208&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking][https_www.nowcoder.com_practice_253d2c59ec3e4bc68da16833f79a38e4_tpId_13_tqId_11208_tPage_3_rp_3_ru_ta_coding-interviews_qru_ta_coding-interviews_question-ranking]

#### 题目描述 ####

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

#### 解决方法 ####

采取双指针，慢指针一次走一步，快指针一次走两步，出现重复之后，表示有环；  
慢指针此时返回到头结点，快指针继续（假设环中有n个结点，则此时快指针比慢指针刚好多走了n步；两者每次都走一步，直到相遇，相遇的地方就是环的第一个节点了

/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } }; */
    class Solution { 
    public:
        ListNode* EntryNodeOfLoop(ListNode* pHead)
        { 
            if (!pHead || !pHead->next) return nullptr;
            //采取双指针，慢指针一次走一步，快指针一次走两步，出现重复之后，表示有环；
            //慢指针此时返回到头结点，快指针继续（假设环中有n个结点，则此时快指针比慢指针刚好多走了n步），
            //两者每次都走一步，直到相遇，相遇的地方就是环的第一个节点了
            ListNode *slow=pHead, *fast=pHead;
            while(fast && fast->next){ 
                slow=slow->next;
                fast=fast->next->next;
                if (slow==fast) {  //说明有环
                    slow=pHead;
                    while(slow && fast){ 
                        if (slow==fast) return slow;
                        slow=slow->next;
                        fast=fast->next;
                    }
                }
            }
            return nullptr;
        }
    };

[https_www.nowcoder.com_practice_253d2c59ec3e4bc68da16833f79a38e4_tpId_13_tqId_11208_tPage_3_rp_3_ru_ta_coding-interviews_qru_ta_coding-interviews_question-ranking]: https://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4?tpId=13&tqId=11208&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking