[数据结构与算法]【快慢指针】142. 环形链表 II

【快慢指针】142. 环形链表 II

题目

解析

        // 快慢指针法：给定两个指针，分别命名为slow fast 起始位置在链表的开头
        // 每次fast前进两步，slow前进一步。如果fast可以走到尽头，那么说明没有环路；
        // 如果fast 可以无限的走下去说明一定有环路，且一定存在某一个时刻slow与fast相遇。当slow和fast
        // 第一次相遇的时候,fast重新移动到链表开头，并让slow和fast每一次都前进一步。当slow和fast第二次相遇
        // 相遇的节点即为环路的开始点

代码

/**
 * 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) {
        // 快慢指针法：给定两个指针，分别命名为slow fast 起始位置在链表的开头
        // 每次fast前进两步，slow前进一步。如果fast可以走到尽头，那么说明没有环路；
        // 如果fast 可以无限的走下去说明一定有环路，且一定存在某一个时刻slow与fast相遇。当slow和fast
        // 第一次相遇的时候,fast重新移动到链表开头，并让slow和fast每一次都前进一步。当slow和fast第二次相遇
        // 相遇的节点即为环路的开始点

        ListNode *slow = head,*fast = head;

        // 判断是否存在环路
         do{
             // 说明不存在环路
             if(!fast || !fast->next) return nullptr;// 因为链表每次走两步 所以fast指针最后可能为空 

             fast = fast->next->next;
             slow = slow->next;

         }while(fast != slow);

         // fast与slow相遇 说明存在环路


         // 让fast 指向head 再一次遍历
         fast = head;

         while(fast != slow)
         {
             slow = slow->next;
             fast = fast->next;
         }

        return fast;
    }
};