C++实现LeetCode(142.单链表中的环之二)

[LeetCode] 142. Linked List Cycle II 单链表中的环之二

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

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Note: Do not modify the linked list.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:

Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.

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

这个求单链表中的环的起始点是之前那个判断单链表中是否有环的延伸，可参之前那道 Linked List Cycle。这里还是要设快慢指针，不过这次要记录两个指针相遇的位置，当两个指针相遇了后，让其中一个指针从链表头开始，一步两步，一步一步似爪牙，似魔鬼的步伐。。。哈哈，打住打住。。。此时再相遇的位置就是链表中环的起始位置，为啥是这样呢，这里直接贴上热心网友「飞鸟想飞」的解释哈，因为快指针每次走2，慢指针每次走1，快指针走的距离是慢指针的两倍。而快指针又比慢指针多走了一圈。所以 head 到环的起点+环的起点到他们相遇的点的距离 与 环一圈的距离相等。现在重新开始，head 运行到环起点 和 相遇点到环起点 的距离也是相等的，相当于他们同时减掉了 环的起点到他们相遇的点的距离。代码如下：

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

Github 同步地址：

https://github.com/grandyang/leetcode/issues/142

类似题目：

Linked List Cycle

Find the Duplicate Number

参考资料：

https://leetcode.com/problems/linked-list-cycle-ii/

https://leetcode.com/problems/linked-list-cycle-ii/discuss/44793/O(n)-solution-by-using-two-pointers-without-change-anything

到此这篇关于C++实现LeetCode(142.单链表中的环之二)的文章就介绍到这了,更多相关C++实现单链表中的环之二内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C++实现LeetCode(104.二叉树的最大深度)

    [LeetCode] 104. Maximum Depth of Binary Tree 二叉树的最大深度 Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. Note: A leaf is a node with no child

  • C++实现LeetCode(889.由先序和后序遍历建立二叉树)

    [LeetCode] 889. Construct Binary Tree from Preorder and Postorder Traversal 由先序和后序遍历建立二叉树 Return any binary tree that matches the given preorder and postorder traversals. Values in the traversals pre and post are distinct positive integers. Example 1

  • C++实现LeetCode(105.由先序和中序遍历建立二叉树)

    [LeetCode] 105. Construct Binary Tree from Preorder and Inorder Traversal 由先序和中序遍历建立二叉树 Given preorder and inorder traversal of a tree, construct the binary tree. Note: You may assume that duplicates do not exist in the tree. For example, given preor

  • C++实现LeetCode(108.将有序数组转为二叉搜索树)

    [LeetCode] 108.Convert Sorted Array to Binary Search Tree 将有序数组转为二叉搜索树 Given an array where elements are sorted in ascending order, convert it to a height balanced BST. For this problem, a height-balanced binary tree is defined as a binary tree in wh

  • C++实现LeetCode(109.将有序链表转为二叉搜索树)

    [LeetCode] 109.Convert Sorted List to Binary Search Tree 将有序链表转为二叉搜索树 Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST. For this problem, a height-balanced binary tree is defined as a binary

  • C++实现LeetCode(103.二叉树的之字形层序遍历)

    [LeetCode] 103. Binary Tree Zigzag Level Order Traversal 二叉树的之字形层序遍历 Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between). For example

  • C++实现LeetCode(106.由中序和后序遍历建立二叉树)

    [LeetCode] 106. Construct Binary Tree from Inorder and Postorder Traversal 由中序和后序遍历建立二叉树 Given inorder and postorder traversal of a tree, construct the binary tree. Note: You may assume that duplicates do not exist in the tree. For example, given ino

  • C++实现LeetCode(143.链表重排序)

    [LeetCode] 143.Reorder List 链表重排序 Given a singly linked list L: L0→L1→-→Ln-1→Ln, reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→- You may not modify the values in the list's nodes, only nodes itself may be changed. Example 1: Given 1->2->3->4, reorder it t

  • C++实现LeetCode(142.单链表中的环之二)

    C++实现LeetCode(142.单链表中的环之二)

    [LeetCode] 142. Linked List Cycle II 单链表中的环之二 Given a linked list, return the node where the cycle begins. If there is no cycle, return null. To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexe

  • C++实现LeetCode(141.单链表中的环)

    C++实现LeetCode(141.单链表中的环)

    [LeetCode] 141. Linked List Cycle 单链表中的环 Given a linked list, determine if it has a cycle in it. To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to.

  • python实现单链表中删除倒数第K个节点的方法

    本文实例为大家分享了python实现单链表中删除倒数第K个节点的具体代码,供大家参考,具体内容如下 题目: 给定一个链表,删除其中倒数第k个节点. 代码: class LinkedListAlgorithms(object): def __init__(self): pass def rm_last_kth_node(self, k, linked_list): # 删除倒数第 K 个节点,针对单链表的 if linked_list.is_empty(): print 'The given li

  • java实现单链表中的增删改

    java实现单链表中的增删改

    本文实例为大家分享了java实现单链表中增删改的具体代码,供大家参考,具体内容如下 什么是链表 链表是有序的列表,但是它在内存中是存储如下 小结: 链表是以节点的方式来存储,是链式存储 每个节点包含data 域, next 域:指向下一个节点. 如图:发现链表的各个节点不一定是连续存储. 链表分带头节点的链表和没有头节点的链表,根据实际的需求来确定 单链表(带头结点) 逻辑结构示意图如下 单链表的增删改应用实例 使用带head 头的单向链表实现——三国英雄排行榜管理完成对英雄人物的增删改查操作

  • C++实现LeetCode(186.翻转字符串中的单词之二)

    [LeetCode] 186. Reverse Words in a String II 翻转字符串中的单词之二 Given an input string , reverse the string word by word.  Example: Input:  ["t","h","e"," ","s","k","y"," ","i&qu

  • java实现单链表中是否有环的方法详解

    这是一道微软经典笔试题,就是两个指针h1,h2都从头开始遍历单链表,h1每次向前走1步,h2每次向前走2步,如果h2碰到了NULL,说明环不存在:如果h2碰到本应在身后的h1说明环存在(也就是发生了套圈). 如果环不存在,一定是h2先碰到NULL: 如果环存在,h2与h1一定会相遇,而且相遇的点在环内:h2比h1遍历的速度快,一定不会在开始的那段非环的链表部分相遇,所以当h1,h2都进入环后,h2每次移动都会使h2与h1之间在前进方向上的差距缩小1,最后,会使得h1和h2差距减少为0,也即相遇

  • Python实现单链表中元素的反转

    Python实现单链表中元素的反转

    给定一个单链表,将其反转.其实很容易想到,只需要修改每个结点的指针指向:即令后一个结点指向前一个结点,并且将表头指针指向最后一个结点即可. 这个过程可以用循环实现,也可以用递归来实现. 1.用循环来实现: class LNode:     def __init__(self, elem):         self.elem = elem         self.pnext = None   def reverse(head):     if head is None or head.pnex

  • C语言中如何实现单链表删除指定结点

    目录 单链表删除指定结点 链表的删除结点(各种方法) 链表中删除第i个结点 删除与链表中与a相同的结点 删除链表中重复元素 单链表删除指定结点 在单链表中删除指定的结点.这里单链表是用尾插法建立的,因为尾插法输出的顺序与输入的顺序是相同的. #include <bits/stdc++.h> using namespace std; typedef struct node { int data; struct node *next; }no; int main() { no *head,*tai

  • 一篇文章带你玩转JAVA单链表

    一篇文章带你玩转JAVA单链表

    目录 一.链表 1. 概念 2. 结构 二.单向不带头非循环链表 1. 概念及结构 2. 链表的实现 三.链表面试题 四.总结 一.链表 1. 概念 链表是一种物理存储结构上非连续的存储结构,数据元素的逻辑顺序是通过链表中的引用链接次序实现的 上章介绍到顺序表适合用作查询和修改,而不适合用作插入和删除.并且它增容时容易造成空间浪费.而链表则具有以下的特点 适合用作插入和删除随用随取,避免了空间的浪费不适合用作查询和修改 2. 结构 链表其实可以想象成一条被打了一些结的绳子 而实际上,链表就是由一

  • Node.js环境下JavaScript实现单链表与双链表结构

    单链表(LinkedList)的javascript实现 npmjs相关库: complex-list.smart-list.singly-linked-list 编程思路: add方法用于将元素追加到链表尾部,借由insert方法来实现: 注意各个函数的边界条件处理. 自己的实现: SingleNode.js (function(){ "use strict"; function Node(element){ this.element = element; this.next = n

随机推荐