[Leecode] Linked List Cycle 链表环

includecmath 发布于2019-08-14 12:27 / 419人阅读

摘要：快慢指针法复杂度时间空间思路这是一道非常经典的双指针题。如果快指针和慢指针相遇，则说明链表有环。代码快慢指针法复杂度时间空间思路这题是基于上一题，上一题我们发现相遇后就返回了，而这里我们还要继续找到环的起始点。

Linked List Cycle I

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

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

快慢指针法 复杂度

时间 O(N) 空间 O(1)

思路

这是一道非常经典的双指针题。我们从头设置一个快指针，一个慢指针。快指针一次走两步，慢指针一次走一步，如果快指针走到了尽头，则说明链表无环。如果快指针和慢指针相遇，则说明链表有环。为什么相遇就说明有环呢？设想一个有环链表，快慢指针最后都会走到环上，而这个环就像一个环形跑道一样，慢指针在后面，快指针在前面，但实际上快指针也在追慢指针，希望能超慢指针一圈。他们在这个跑道上，总会有一天快指针追上了慢指针。我们不用担心快指针跳过了慢指针，因为他们两的速度差是1，所以她们俩在环上的距离总是每次减1，最后总能减到0。

代码

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

2018/10

func hasCycle(head *ListNode) bool {
    fast := head
    slow := head
    // if fast.Next == nil and fast != slow, there can"t be a cycle
    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
        if fast == slow {
            return true
        }
    }
    return false
}

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?

快慢指针法 复杂度

时间 O(N) 空间 O(1)

思路

这题是基于上一题，上一题我们发现相遇后就返回true了，而这里我们还要继续找到环的起始点。假设快慢指针在环上第k个节点相遇，而环的起点是链表第m个节点，环的总长度是n。此时慢指针再走n-k步就回到了环的开头，而此时快指针已经走了m+k步。如果我们这时候将快指针放回起点，并让它也一次走1步，这样当两个节点再次相遇时，相遇点就是环的起点。

代码

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                // 找相遇点
                slow = head;
                while(slow != fast){
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow;
            }
        }
        return null;
    }
}

GPU云服务器云服务器 Leecode linked Cycle jquery cycle js

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

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

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 141：环形链表 Linked List Cycle

摘要：给定一个链表，判断链表中是否有环。示例输入输出解释链表中有一个环，其尾部连接到第一个节点。哈希表解决重复问题最容易想到的数据结构就是哈希表，哈希表添加节点时只要发现节点已经存在了，证明就有环形链表。给定一个链表，判断链表中是否有环。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。 Giv...

chenjiang3 2019-08-16 18:35 评论0 收藏0
LeetCode 141：环形链表 Linked List Cycle

摘要：给定一个链表，判断链表中是否有环。示例输入输出解释链表中有一个环，其尾部连接到第一个节点。哈希表解决重复问题最容易想到的数据结构就是哈希表，哈希表添加节点时只要发现节点已经存在了，证明就有环形链表。给定一个链表，判断链表中是否有环。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。 Giv...

ysl_unh 2019-07-31 11:28 评论0 收藏0