How to judge whether a linked list has links

Degree 123 2021-05-03 19:16:12
judge linked list links


If you judge that the linked list has links ? The following list

solution 1:

Double loop traversal , Every time you traverse a new node , Just go ahead and find out if this node ever existed , Time complexity O(n2), Spatial complexity O(1)

solution 2:

But loop traversal , No traversal of a node , Just deposit the object , Traversing a new node is to find out whether the node exists in the object , Time complexity O(n), Spatial complexity O(n)

solution 3:

Set two pointers ,p1、p2, Point to the node head , Next, every time you let p1 One node forward ,p2 Two nodes ahead , If the list has rings , be p2、p1 Then it will overlap , Point to the same node

Time complexity O(n), Spatial complexity O(1)

The code is as follows :

 /**
* @param {*} head Chain header node
* @description Determine if the list has links
*/
function isCycle(head:LinkNodeType | null):boolean {
let p1 = head;
let p2 = head;
while(p2!==null && p2.next !== null && p1 !== null) {
p2 = p2.next.next;
p1 = p1.next;
if(p2 === p1) {
return true
}
}
return false
};
function main() {
let node1 = new LinkNode(5)
let node2 = new LinkNode(3)
let node3 = new LinkNode(7)
let node4 = new LinkNode(2)
let node5 = new LinkNode(6)
let node6 = new LinkNode(8)
let node7 = new LinkNode(1)
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
node5.next = node6;
node6.next = node7;
node7.next = node5;
console.log(isCycle(node1))
}
main()
 Copy code 

Expand :

1. If the list has links , Find the length of the ring

solution : When the two hands meet for the first time , Prove that a linked list has rings , Now let the pointer go on , Until the second meeting , here , The fast pointer goes one more turn than the slow one

The code is as follows :

 /**
* @param {(LinkNodeType | null)} head
* @returns {(boolean|number)}
* @description Determine if the list has links , How to have a ring Find the ring length
*/
function cycleLength(head: LinkNodeType | null):boolean|number {
let p1 = head;
let p2 = head;
let isFirst = true;
let length = 0
while(p1 !== null&& p2 !== null && p2.next !== null) {
p2 = p2.next.next;
p1 = p1.next;
if(!isFirst) {
length ++
}
if(p2 == p1 && !isFirst) {
return length
}
if(p2 == p1) {
isFirst = false
}
}
return false
}
 Copy code 

2. If the list has links , Find the access point

Explain :

As follows

p1 The distance of the pointer is D + S1

p1 The distance of the pointer is D + S1 + S2 + S1 = D + S2 + 2S1

Again because p2 The speed of the pointer is 2,p1 The speed of the pointer is 1 therefore

D + S2 + 2S1 = 2(D + S1)

D + S2 + 2S1 = 2D + 2S1

D + S2 = 2D

D = S2

therefore , When two nodes meet for the first time , Get the node , Set two pointers p1 p2 Put them in the head of the chain , And meeting nodes , Go in turn 1, Then the meeting point is Entry point

The code is as follows :

 /**
* @param {*} head Chain header node
* @description Determine if the list has links
*/
function isCycle(head:LinkNodeType | null):boolean | LinkNode {
let p1 = head;
let p2 = head;
while(p2!==null && p2.next !== null && p1 !== null) {
p2 = p2.next.next;
p1 = p1.next;
if(p2 === p1) {
return p1 as LinkNode
}
}
return false
};
/**
* @param {*} firstDot The first meeting point
* @returns Entry point
*/
function cycleDot(firstDot:LinkNode,headDot:LinkNode):LinkNode {
let p1 = firstDot;
let p2 = headDot;
while(p1 !== p2) {
p1 = p1.next as LinkNode;
p2 = p2.next as LinkNode;
}
return p1
}
function main() {
let node1 = new LinkNode(5)
let node2 = new LinkNode(3)
let node3 = new LinkNode(7)
let node4 = new LinkNode(2)
let node5 = new LinkNode(6)
let node6 = new LinkNode(8)
let node7 = new LinkNode(1)
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
node5.next = node6;
node6.next = node7;
node7.next = node4;
let firstNode = isCycle(node1)
if(firstNode){
console.log(cycleDot(firstNode as LinkNode, node1))
}
}
 Copy code 

Summary from : Comics algorithm Xiaohui's algorithm tour

版权声明
本文为[Degree 123]所创,转载请带上原文链接,感谢
https://qdmana.com/2021/05/20210503191542338n.html

  1. CSS layout
  2. Application scenario explanation of Vue dynamic component
  3. Redux learning notes 04 -- using multiple reducers to manage data
  4. After three months of typescript writing, what have I learned?
  5. Node family - what is a callback?
  6. React -- a simple implementation of render & create element
  7. JS learning simple usage of jquery
  8. Seamless love
  9. 小白前端入门笔记(12),设置哑链接
  10. Small white front-end entry notes (12), set dumb links
  11. Vue2. X opens composition API and TSX
  12. Interview record and thinking of social recruitment for one and a half years (Alibaba, Tencent, baidu offer)
  13. Flex learning notes
  14. The most essential closure article in the eastern hemisphere
  15. 2021-05-03 hot news
  16. Sword finger offer -- reverse order pair in array (JS Implementation)
  17. Working process of scaffold
  18. Use decorator mode to strengthen your fetch
  19. [JS] scope (Introduction)
  20. Employment information statistics network (interface document)
  21. Analysis of MVC
  22. [middle stage] please stay and join me in the backstage
  23. Understanding front end garbage collection
  24. [continuous update] front end special style implementation
  25. Flutter product analysis and package reduction scheme
  26. XPath positioning
  27. 前端开发css中的flex布局的使用
  28. The use of flex layout in front end development CSS
  29. JQuery核心函数和静态方法
  30. JQuery core functions and static methods
  31. Node family - understanding of blocking and non blocking
  32. 热点微前端Microfrontend的讨论:谷歌AdWords是真实的微前端
  33. Vue source code analysis (2) initproxy initialization proxy
  34. What's TM called react diff
  35. Summary of common front end data structure
  36. Useeffect in hooks
  37. [encapsulation 02 design pattern] Command pattern, share meta pattern, combination pattern, proxy pattern, strategy pattern
  38. Front end notes: virtual Dom and diff of vue2. X
  39. The best code scanning plug-in of flutter
  40. The simplest plug-in for rights management of flutter
  41. 21. Object oriented foundation "problems and solutions of object traversal"
  42. Discussion on hot micro front end: Google AdWords is a real micro front end
  43. Usecallback and usememo for real performance optimization
  44. 【前端圭臬】十一:从规范看 JavaScript 执行上下文(下)
  45. [front end standard] 11: Javascript execution context from the perspective of specification (2)
  46. Hexagonal六角形架构ReactJS的实现方式 - Janos Pasztor
  47. Transaction of spring's reactive / imperative relational database
  48. The implementation of hexagonal hexagonal reactjs Janos pasztor
  49. HTTP状态码:402 Payment Required需要付款 - mozilla
  50. HTTP status code: 402 payment required - Mozilla
  51. Factory mode, constructor mode and prototype mode
  52. Build the scaffold of react project from scratch (Series 1: encapsulating a request method with cache function based on Axios)
  53. Cocos Quick Start Guide
  54. Comparison of three default configurations of webpack5 modes
  55. A case study of the combination of flutter WebView and Vue
  56. CSS: BFC and IFC
  57. A common error report and solution in Vue combat
  58. JS: this point
  59. JS: prototype chain
  60. JavaScript series -- promise, generator, async and await