当前位置:网站首页>Sword finger offer II 022 Entry node of a link in a linked list
Sword finger offer II 022 Entry node of a link in a linked list
2022-06-13 03:58:00 【Smoothzjc】
The finger of the sword Offer II 022. The entry node of a link in a list
difficulty : secondary
Given a linked list , Return to the first node of the link where the list begins to enter . Start from the head node of the linked list next The first node where the pointer enters the ring is the entry node of the ring . If the list has no links , Then return to null.
To represent a ring in a given list , We use integers pos To indicate where the end of the list is connected to the list ( Index from 0 Start ). If pos yes -1, There are no links in the list . Be careful ,pos It's just for identifying rings , It's not passed to the function as an argument .
explain : It is not allowed to modify the given linked list .
Example 1:
Input :head = [3,2,0,-4], pos = 1
Output : The return index is 1 The linked list node of
explain : There is a link in the list , Its tail is connected to the second node .
Example 2:
Input :head = [1,2], pos = 0
Output : The return index is 0 The linked list node of
explain : There is a link in the list , Its tail is connected to the first node .
Example 3:
Input :head = [1], pos = -1
Output : return null
explain : There are no links in the list .
Tips :
The number of nodes in the list is in the range [0, 104] Inside
-105 <= Node.val <= 105
pos The value of is -1 Or a valid index in a linked list
1. Speed pointer
Ideas : We use two pointers . They all start at the head of the linked list . And then ,slow The pointer moves back one position at a time , and fast The pointer moves back two positions . If there are rings in the list , be fast The pointer will end up with slow The pointer meets in the ring . Let the length of the outer part of the link in the linked list be a.slow After the pointer enters the ring , Gone again bb The distance between fast meet . here ,fast The pointer has gone through the ring n circle , So the total distance it has traveled is a+n(b+c)+b=a+(n+1)b+nca+n(b+c)+b=a+(n+1)b+nc. According to the meaning , Anytime ,fast The distance traveled by the pointer is slow Pointer 2 times . therefore , We have
a+(n+1)b+nc=2(a+b)*a=c+(n−1)(b+c)
With a=c+(n-1)(b+c)a=c+(n−1)(b+c) The equivalence of , We will find that : The distance from the meeting point to the entry point plus n-1 Ring length of circle , Exactly equal to the distance from the head of the linked list to the ring entry point .
therefore , If I found slow And fast When we met , Let's use an extra pointer ptr. start , It points to the head of the linked list ; And then , It and slow Move back one position at a time . Final , They will meet at the entry point .
The code is as follows
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */
/** * @param {ListNode} head * @return {ListNode} */
var detectCycle = function(head) {
let slow = head;
let fast = head;
while(fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if(slow === fast) {
// Description ring
let ptr = head;
while (ptr !== slow) {
ptr = ptr.next;
slow = slow.next;
}
return ptr;
}
}
return null;
};
The time and space complexity are shown in the figure 
2. Hashtable
Ideas : Hash tables are easier to understand , Each node in the traversal linked list is stored in the hash table , If you traverse to a duplicate , That proves there is a ring ( Numerical repetition does not affect , namely 2 individual 2 or 3 individual 2 Will not interfere with the results , Because they val Same but next Different )
The code is as follows
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */
/** * @param {ListNode} head * @return {ListNode} */
var detectCycle = function(head) {
if(!head) return null;
let set = new Set();
let p = head;
while(p) {
if(set.has(p)) return p;
set.add(p);
p = p.next;
}
return null;
};
The time and space complexity are shown in the figure 
边栏推荐
- SCM: introduction and operation of EEPROM
- Common array methods in JS (map, filter, foreach, reduce)
- Lambda终结操作count
- 高等数学(第七版)同济大学 习题1-3 个人解答
- Use lodash to merge the values of the same fields in an array object
- [test development] file compression project practice
- Lambda终结操作查找与匹配noneMatch
- GoFrame第四天
- 【測試開發】自動化測試selenium(三)——unittest框架解析
- Lambda终结操作max&min
猜你喜欢

【Web】Cookie 和 Session

单片机:A/D 和 D/A 的基本概念
![[zeloengine] localization process /imgui Chinese culture](/img/ec/7eb7edc236b09994c2981e6f13dc68.png)
[zeloengine] localization process /imgui Chinese culture

Jumpserver: user - system privileged user - Asset - authorization

Solution to failure to download files by wechat scanning QR code

单片机:RS485 通信与 Modbus 协议

Fundamentals of robot obstacle avoidance system

Wechat payment configuration

单片机:PCF8591 应用程序

UnionPay commerce - merchant statistics service platform
随机推荐
Lambda终结操作查找与匹配findAny
【测试开发】软件测试基础篇
单片机:A/D 和 D/A 的基本概念
Flex layout
单片机:红外遥控通信原理
SCM: introduction and operation of EEPROM
机器人避障系统基础
Alibaba cloud keep on record
Lambda终结操作查找与匹配findFirst
单片机:Modbus 通信协议介绍
[test development] installation of test management tool Zen path
[test development] blog system - LoadRunner performance test (publish blog function benchmark test)
V-bind and v-on
Single chip microcomputer: main index of a/d (analog-to-digital conversion)
Lambda termination operation find and match nonematch
十億數據量 判斷元素是否存在
[笔记]vs2015 编写汇编masm32之使用MASM32库
Among the four common technologies for UAV obstacle avoidance, why does Dajiang prefer binocular vision
任总与系统工程领域科学家、专家会谈纪要
Lambda end operation find and match findany