27
2017
09

142. 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?


141. Linked List Cycle。的升级版本。需要找出进入环的那个节点所在。第一种还是使用之前的集合方法,定义一个set集合并遍历链表,如果当前节点不存在set中则将节点存放进去,如果存在了这说明这个节点就是进入环的位置。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        unordered_set<ListNode*> nodes;
        while(head) {
            if(nodes.count(head)==1) {
                return head;
            } else {
                nodes.insert(head);
            }
            head = head->next;
        }
        return NULL;
    }
};

第二种使用的是赋值的方法,遍历每个节点,然后将节点的值赋值为INT_MAX,那么遇到下一次的节点值等于INT_MAX时候就是环的入口。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {

        while(head) {
            if(head->val != INT_MAX) {
                head->val = INT_MAX;
            } else {
                return head;
            }
            head = head->next;
        }

        return NULL;
    }
};

第三种是使用快慢指针的方法,先来画一个图。

这里写图片描述

图中分为了三个阶段A为链表的起点,B为环的入口,如果使用快慢指针的话,快的指针先进入环,然后慢的指针进入。这个时候可以看成快的指针在追赶慢的指针,假设快指针在C处追到了慢指针。此时相当于是快指针已经饶了环一圈了,那么快指针走的路就是1+2+3+2,而慢指针走的路是1+2。并且因为快指针走的路是慢指针的两倍,所以能够得出3=1.既然1和3的路是相等的,就可以使用两个指针分别从A点和C点出发,当他们相遇的时候就是走了图中1(或者3)的距离,而从链表的起点A到环的入口点B正好距离就是1,所以此时相遇的节点就是环的入口。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {

        //快慢指针

        if(!head) return nullptr;

        ListNode* slow = head;
        ListNode* fast = head;
        ListNode* entry = head;

        while(fast->next && fast->next->next) {
            fast = fast->next->next;
            slow = slow->next;

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

        }

        return nullptr;
    }
};
上一篇:86. Partition List。 下一篇:《Android开发艺术探索》之消息机制(一)