链表中环的入口节点

ryluo 2020-06-27 11:10:38

给定一个链表,若其中包含环,则输出环的入口节点。

若其中不包含环,则输出null

样例

QQ截图20181202023846.png

给定如上所示的链表:
[1, 2, 3, 4, 5, 6]
2
注意,这里的2表示编号是2的节点,节点编号从0开始。所以编号是2的节点就是val等于3的节点。

则输出环的入口节点3.

分析:

使用快慢指针。快指针每次走两步,慢指针每次走一步,直到快慢指针相遇之后,让慢指针回到起始点,然后快慢指针每次都走一步,直到再次相遇,此次相遇的节点就是环的入口

详细的题解:

https://www.acwing.com/solution/content/741/

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *entryNodeOfLoop(ListNode *head) {
        auto fast = head, slow = head;
        while(fast && slow){
            fast = fast->next;
            slow = slow->next;
            if(fast) fast = fast->next;

            if(fast == slow){
                slow = head;
                while(slow != fast){
                    fast = fast->next;
                    slow = slow->next;
                }
                return fast;
            }
        }
        return NULL;
    }
};