原题:
Given a linked list, return the node where the cycle begins. If there is no cycle, returnnull
.
=>找到单向链表的环的起点,若没有环,返回null
Follow up:
Can you solve it without using extra space?
=>能否不使用额外的空间。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
}
};
晓东分析:
看单向链表中是否存在环,晓东之前已经讲过了。这篇文章主要讲一下,如何找到这个环的起点,其实方法很简单,就是在快慢指针相交的时候,把快指针移到开始,然后大家都以1步的步长开始运动,再次遇到的时候就是环的起点。如何来证明这个做法呢,晓东来简单讲解一下。假设如下图:
我们假设快慢指针相会于C点。这个时候他们走过的路程:
快指针路程=慢指针路程+N*圆的周长=AB的距离+BC距离+M*圆的周长(M和N都是整数,不一定相等)
而我们知道快指针的路程,其实是慢指针路程的两倍。
也就是说:
快指针路程=2*慢指针的路程
所以2*慢指针的路程=慢指针路程+N*圆的周长
所以,慢指针路程=N*圆的周长。
代入上式得到:
2*N圆的周长=AB的距离+BC距离+M*圆的周长
所以AB的距离+BC距离=L*圆的周长
所以AB的距离= L*圆的周长-BC距离。
因此,我们从C点开始的慢指针,和从A点开始的慢指针肯定会相遇于B点。
代码实现:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
if(head == NULL || head->next == NULL) return NULL;
ListNode *fast = head->next->next;
ListNode *slow = head->next;
while(fast != slow && fast != NULL && fast->next != NULL)
{
fast = fast->next->next;
slow = slow->next;
}
if(fast == NULL || fast->next == NULL)
return NULL;
fast = head;
while(fast != slow){
fast = fast->next;
slow = slow->next;
}
return fast;
}
};
运行结果:
16 / 16test cases passed.
|
Status:
Accepted
|
Runtime: 68 ms
|
希望大家有更好的算法能够提出来,不甚感谢。
若您觉得该文章对您有帮助,请在下面用鼠标轻轻按一下“顶”,哈哈~~·
分享到:
相关推荐
链表版的软件工程师管理系统,可以对工程师的信息进行增删改查
142-环形链表:linked-list-cycle-ii 160-相交链表:intersection-of-two-linked-lists 206-反转一个单链表:reverse-linked-list 20-有效的括号:valid-parentheses 150-逆波兰表达式求值:evaluate-reverse-polish-...
preorder-traversal链表reorder-list链表linked-list-cycle-ii链表linked-list-cycle动态规划word-break-ii动态规划word-break链表copy-list-with-random-pointer复杂度single-number-ii复杂度single-number动态规划
各种数据结构、算法及实用的C#源代码.C#,单向链表(Simply Linked List)快速排序(Quick Sort)算法与源代码.单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部...
leetcode中325题python leetcode 以 参考 和 Hash相关 1_两数之和 ...linked-list-cycle-ii 143 重排链表 reorder-list 148 排序链表 sort-list 234 回文链表 palindrome-linked-list 双指针遍历/滑动
linked-list-cycle-ii 链表 linked-list-cycle 链表 copy-list-with-random-pointer 复杂度 single-number 动态规划 candy 贪心 gas-station 动态规划 palindrome-partitioning-ii 动态规划 triangle 树 sum-root-to...
单向链表 Go 中的单向链表
leetcode伪代码convert-binary-number-in-a-linked-list-to-integer 题目解读: 题目来源: 原文: Given head which is a reference node to a singly-linked list. The value of each node in the linked list is ...
Linked list clean-up function.Your function deletes all the values less than x the list.
Leetcode.92.反转链表 II* Definition for singly-linked list.ListNode* reverseBetween
单向循环链表代码,参考我的博客:https://blog.csdn.net/weixin_45571585/article/details/127724891?spm=1001.2014.3001.5502
题目地址:思路反转链表难度大得多代码* Definition for singly-linked list.* function ListNode(val, n
C#,单向链表(Simply Linked List)的归并排序(Merge Sort)算法与源代码 归并排序法(3Merge Sort,以下简称MS)是分治法思想运用的一个典范。 其主要算法操作可以分为以下步骤: Step 1:将n个元素分成两个含n/...
编写一个函数来删除单向链表中的节点(尾部除外),只允许访问该节点。 给定链表——head = [4,5,1,9]。 Example 1: Input: head = [4,5,1,9], node = 5 Output: [4,1,9] Explanation: You are given the second ...
数据结构,单链表 ,逆序输出,数据结构,单链表 ,逆序输出
linked-list-ts:打字稿链表实现
前端开源库-dbly-linked-list双链表,双链表数据结构的javascript实现
C#,单向链表(Simply Linked List)的插入排序(Insertion Sort)算法与源代码 所谓插入排序法乃是将一个数目插入该占据的位置。 假设我们输入的是 “5,1,4,2,3” 我们从第二个数字开始,这个数字是1,我们的...
1,单向链简洁。...根据示例代码中的例子,完成单向链表(single linked list)中的以字符串为数据的链表的插入、删除以及查找,并支持单向链表的反转; 3,代码实现。 #include #include <math.h>
基于python的数据结构-链表Linked list