[leetcode题解]142.Linked List Cycle II(python + c++)

leetcode第142题,linked list cycle ii,前面有道题目是判断单链表是否有环。
本题就是将上个题目进行改进,首先判断是否有环,如果有环则返回环的入口节点,如果没有环的话返回NULL。
本题的解法首先按照上篇文章中提到的快慢指针法来判断环,并返回快慢指针相遇的节点。
然后,将一个指针从头开始,另一个指针从相遇节点开始,一步一步走下去,直到两者相遇的点就是环的入口节点。
直接这样说不太好想,可以用数学的方法推导下,就能得出这个结论。
如上图,链表头部到环入口的距离为x,环入口到相遇的节点的距离为d,环的长度为y。则根据快慢指针的走法可以得到:

2*(x + d) = (x + d) + n * y   //n为大于等于1的整数
化简得到x + d = n * y  ==>  x = (n - 1) * y + (y - d)

所以,x的长度正好是环上相遇点剩余的距离加上0或者任意整数圈后的距离。也就是两者分别从相遇点和头开始,一定会在入口点处相遇。

c++和python代码如下:

c++代码:

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *cycle = hasCycle(head);
        if (cycle == NULL)return NULL;
        
        ListNode *p = head;
        while(cycle != p)
        {
            cycle = cycle->next;
            p = p->next;
        }
        return p;
    }
    
    ListNode *hasCycle(ListNode *head)
    {
        if (head == NULL || head->next == NULL)return NULL;
        ListNode *slow = head, *fast = head;
        
        while(fast->next != NULL && fast->next->next != NULL)
        {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast)return slow;
        }
        return NULL;
    }
};

python代码:

class Solution(object):

    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        node = self.hasCycle(head)
        if node == None:
            return None
        while head != node:
            head = head.next
            node = node.next
        return node

    def hasCycle(self, head):
        if head == None or head.next == None:
            return None
        slow = head
        fast = head
        while fast.next != None and fast.next.next != None:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return slow
        return None

本文遵从CC3.0协议转载请注明:转自凌风技术站

本文标题:[leetcode题解]142.Linked List Cycle II(python + c++)

本文链接地址:http://www.iaccepted.net/algorithm/leetcode/69.html

相关文章



发表评论

电子邮件地址不会被公开。 必填项已用*标注