[LintCode] Linked List Cycle I & II

用户83 发布于2019-08-14 15:17 / 3486人阅读

摘要：做法如果有环，快慢指针必定可以相遇。而让此时重新从起点出发，以和相同的速度，需要走非环路的直线长度，才能到达环的起点。也就是说，，就是第二个循环结束的条件。

Linked List Cycle I Problem

Given a linked list, determine if it has a cycle in it.

Example

Given -21->10->4->5, tail connects to node index 1, return true

Note

做法：如果有环，快慢指针必定可以相遇。
注意两点：初始化快慢指针的时候，fast要在slow后面，也就是head.next；由于fast一次走两步，所以while循环里要判断两个位置是否为null：fast和fast.next。

Solution

public class Solution {
    public boolean hasCycle(ListNode head) {  
        if (head == null/* ||head.next == null */) return false;
        ListNode fast = head.next;
        ListNode slow = head;
        while (fast != slow) {
            if (fast == null || fast.next == null) return false;
            fast = fast.next.next;
            slow = slow.next;
        }
        return true;
    }
}

Linked List Cycle II Problem

Given a linked list, return the node where the cycle begins.

If there is no cycle, return null.

Example

Given -21->10->4->5, tail connects to node index 1，return 10.

Note

画一个简图：

a: length of non-loop 非环直线的长度
b: length of loop     环的长度
x: the point slow and fast meet in the loop 快慢指针在环内相遇的位置

--------oooo
        o  o
        ooxo

(a+x)*2 = a-1+kb+x --> a = kb-1-x, slow needs to go kb-x longer to finish the loop.
so if head wants to go to the start point of the loop, it would pass a, the same for slow. After head went a, slow went kb-x-1. However, a = kb-x-1, so head is slow.next at the loop, which is the start point of the loop.

slow在fast在环里的k处相遇，fast比slow走了两倍的路程，假设非环路和环路长度分别为a和b，且fast已经在环里多走了k圈，所以：
(a+x)*2 = a-1+kb+x --> a = kb-1-x
此时，slow还要走kb-x才能走完整个环。
而让head此时重新从起点出发，以和slow相同的速度，需要走非环路的直线长度a，才能到达环的起点。
那么，head到达环的时候，走了a = kb-1-x：是slow在环内走到环的起点的路程-1。
也就是说，slow.next = head，就是第二个while循环结束的条件。

Solution

public class Solution {
    public ListNode detectCycle(ListNode head) {  
        if (head == null) return null;
        ListNode fast = head.next;
        ListNode slow = head;
        while (fast != slow) {
            if (fast == null || fast.next == null) return null;
            fast = fast.next.next;
            slow = slow.next;
        }
        while (head != slow.next) {
            head = head.next;
            slow = slow.next;
        }
        return head;
    }
}

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65557.html

leetcode141-142. Linked List Cycle I &amp; II

摘要：题目要求这道题目要求判断一个链表中是否有环，如果有环，就返回环中的第一个节点。如果有环，就会重复遇到这个指向的节点。则该链表有环，且该节点就是环的起始节点。但是这个方法会毁坏原来链表的数据结构。题目要求 Given a linked list, return the node where the cycle begins. If there is no cycle, return n...

张巨伟 2019-08-16 10:40 评论0 收藏0
LeetCode 之 JavaScript 解答第142题 —— 环形链表 II（Linked Li

摘要：说明不允许修改给定的链表。算法思路题目要求返回单链表中存在循环链表的位置。首先，先判断该单链表是否存在循环链表用两个快慢指针分别指向链表的头部，每次移动两步，每次移动一步，移动的步数是的两倍。 Time：2019/4/8Title: Linked List Cycle IIDifficulty: mediumAuthor:小鹿题目：Linked List Cycle II Giv...

whidy 2019-08-23 16:51 评论0 收藏0
LeetCode 142：环形链表 II Linked List Cycle II

摘要：如果链表无环，则返回。说明不允许修改给定的链表。示例输入输出解释链表中有一个环，其尾部连接到第一个节点。两种方法哈希表哈希表添加节点时只要发现节点已经存在了，证明就有环形链表。给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该...

hoohack 2019-08-16 18:36 评论0 收藏0
LeetCode 142：环形链表 II Linked List Cycle II

摘要：如果链表无环，则返回。说明不允许修改给定的链表。示例输入输出解释链表中有一个环，其尾部连接到第一个节点。两种方法哈希表哈希表添加节点时只要发现节点已经存在了，证明就有环形链表。给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该...

geekzhou 2019-07-31 11:29 评论0 收藏0
[LeetCode] Reverse Linked List I &amp; II

Reverse Linked List Reverse a singly linked list. Note Create tail = null; Head loop through the list: Store head.next, head points to tail, tail becomes head, head goes to stored head.next; Return t...

jcc 2019-08-14 14:55 评论0 收藏0