欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

剑指Offer——JZ55.链表环的入口结点【快慢指针】

程序员文章站 2022-06-17 16:12:59
...

题目传送门


剑指Offer——JZ55.链表环的入口结点【快慢指针】


题解

  • **解法一:**记录走过的结点,遇到走过的判定为有环
  • 解法二:
    剑指Offer——JZ55.链表环的入口结点【快慢指针】

AC-Code

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        set<ListNode*> st;
        while(pHead) {
            if(st.count(pHead)) {
                return pHead;
            }
            st.insert(pHead);
            pHead = pHead->next;
        }
        return NULL;
    }
};
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        ListNode *fast = pHead;
        ListNode *slow = pHead;
        while (fast && fast->next) {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow) break;
        }
        if (!fast || !fast->next) return nullptr;
        fast = pHead;
        while (fast != slow) {
            fast = fast->next;
            slow = slow->next;
        }
        return fast;
    }
};
相关标签: 剑指Offer