Linked List Cycle

Oct 30, 2017

第35天。

今天的题目是Linked List Cycle II:

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note: Do not modify the linked list.

Follow up: Can you solve it without using extra space?

这道题是判断链表是否有环的升级版。

首先肯定需要fastslow指针来先判断是否有环,如果没有,就直接返回nullptr即可。

然后就是怎么计算出环的入口了。

先来个暴力的方法:

ListNode *detectCycle(ListNode *head) {
    vector<ListNode *> lvec;
    ListNode *fast = head;
    ListNode *slow = head;
    while(fast && fast->next) {
        fast = fast->next->next;
        slow = slow->next;
        //lvec.push_back(slow);
        if (slow == fast) {
            lvec.push_back(slow);
            slow = slow->next;
            while(slow != fast) {
                lvec.push_back(slow);
                slow=slow->next;
            }
            for(auto t:lvec) cout << t->val << endl;
            while(find(lvec.begin(),lvec.end(),head) == lvec.end())
                head = head->next;
            return head;
        }
    }

    return nullptr;
}

当然实际的方法不用那么麻烦:

ListNode *detectCycle(ListNode *head) {
    vector<ListNode *> lvec;
    ListNode *fast = head;
    ListNode *slow = head;
    while(fast && fast->next) {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow) {
            slow = head;
            while(slow != fast) {
                slow = slow->next;
                fast = fast->next;
            }
            return fast;
        }
    }

    return nullptr;
}

emmmm,一直很好奇为什么可以这样判断,就去搜了一下,发现了这个判断单向链表是否有环及求环入口的算法数学证明.

LeetCodeLeetCodeLinked-List

Sort List

Partition to K Equal Sum Subsets

comments powered by Disqus