《剑指offer》JZ23 链表中环的入口结点 两种方法解析

《剑指offer》JZ23 链表中环的入口结点 两种方法解析

今天11.30，现在已经进入12月了，呜呜呜加油

JZ23 链表中环的入口结点

题目链接
大概就是题目会给一个链表，求环（如果尾巴的next指向前面的节点就成环了）
主要有两种解法

1.哈希法

意思就是遍历这个链表，一步一步走，如果没有成环的话没次都会走到不同的结点。用一个容器把走过的结点都存起来，这时候要是走到一个以前走过的结点了，那必然就是又绕到前面去，成了环。
so，在C++的STL容器里面只有set和map有find方法（图省事），我就直接用了set。
上代码：

class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        set st;		//新建一个空的set容器
        while(pHead){			//从链表头开始一步一步往后走
            if(st.find(pHead)!=st.end()){	//如果在容器里能找到当前走到的结点
                return pHead;	//说明之前来过，这个节点就是成环的入口
            }
            st.insert(pHead);	//如果没有找到就把当前的结点加入到容器中
            pHead=pHead->next;  //往后走一步
        }    
        return nullptr;
    }
};

2.双指针（快慢指针）法

这个也不是我想出来的，看的别人的题解然后照着实现了一下，主要有几个步骤：

1. 新建一个fast，一个slow指针均指向头节点
2. fast一次走两步，slow一次走一步
3. 遇到了就停下来，fast重新回到起点
4. fast和slow一次走一步
5. 最后相遇的结点即位相求

最后大概也没去深究是怎么个原理，就自己实现了一下（注意！如果边界条件不考虑会过不了最后一个测试点：题目给了一个空指针或者题目给的指针指向的结点next为空。）

//双指针（快慢指针）方法
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        if(pHead==nullptr||pHead->next==nullptr) return nullptr;
        ListNode* fast = pHead;
        ListNode* slow = pHead;
        while(fast&&slow){
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow) break;
        }
        if(fast == nullptr || slow == nullptr) return nullptr;
        fast = pHead;
        while(fast != slow){
            fast = fast->next; slow = slow->next;
        }
        return slow;
    }
};

总结

这两种方法各有优劣吧，哈希法时间复杂度O(n) 空间复杂度O(n)。双指针法时间O(n) 空间O(1)。如果从哈希法来看就是空间换时间，双指针就是时间换空间（其实最后的运行结果是双指针两个都赢了，深层次的原因我也不知道了）总的来说就是一种权衡吧。我这种懒人来说当然更喜欢哈希法，代码短思维量少。/狗头