One of the most high-frequency algorithm problems in the front end! Reverse linked list

HZFEStudio 2021-10-14 04:09:13
high-frequency high frequency algorithm problems


Complete high frequency question bank warehouse address :https://github.com/hzfe/awesome-interview

Complete high frequency question bank reading address :https://febook.hzfe.org/

Title Description

Define a function , Enter the head node of a linked list , Invert the linked list and output the head node of the inverted linked list .

Example :

 Input : 1->2->3->4->5->NULL
Output : 5->4->3->2->1->NULL

Solution 1 : iteration ( Double pointer )

Online links

This method is to traverse the linked list , Then, when accessing each node, modify next The direction of , Achieve the purpose of reversing the linked list .

  1. initialization cur and pre Two nodes , Point to respectively head and null.
  2. Cycle the linked list , Statement temp Node is used to save the next node of the current node .
  3. Modify the current node cur Of next The pointer points to pre node .
  4. pre Node is modified to cur node .
  5. cur Node is modified to temp node .
  6. Continue processing , until cur The node is null, return pre node .
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
const reverseList = (head) => {
let cur = head; // The head pointer of the forward linked list 
let pre = null; // The head pointer of the reverse linked list 
while (cur) {
const temp = cur.next; // Staging subsequent nodes of the current node , Used to update the forward linked list 
cur.next = pre; // Point the current node to the reverse linked list , This is a process of establishing reverse links 
pre = cur; // Update the header pointer of the reverse linked list to the currently processed node , The construction of this round of reverse linked list is completed 
cur = temp; // Replace the forward chain header pointer with the temporary node , Forward linked list processing completed , Start the next round of processing 
}
return pre;
};

Complexity analysis

  • Time complexity O(N): Traversing the linked list uses linear size time .
  • Spatial complexity O(1): Variable pre and cur Use constant size for extra space .

Solution 2 : recursive

Online links

When using recursion to process linked lists , Start from the first node of the linked list , Then find the last node , This node is the head node of the inverted linked list , Then perform backtracking processing .

  1. The head node of the initial linked list ,head identification .
  2. If head Empty or head.next It's empty , return head.
  3. Definition reverseHead node , Save the inverted linked list value .
  4. Every time you let head Of the next node next Point to head, Form inversion .
  5. Recursive processing to the last node , return reverseHead.
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
const reverseList = (head) => {
// Judge whether the current node still needs to process 
if (head == null || head.next == null) {
return head;
}
// Recursive processing of subsequent nodes 
const reverseHead = reverseList(head.next);
// Local inversion node 
head.next.next = head;
head.next = null;
return reverseHead;
};

Complexity analysis :

  • Time complexity O(N):n It's the length of the list , You need to reverse each node of the linked list .
  • Spatial complexity O(N):n It's the length of the list , The space complexity mainly depends on the stack space of recursive calls , At most n layer .

Reference material

  1. The finger of the sword offer
版权声明
本文为[HZFEStudio]所创,转载请带上原文链接,感谢
https://qdmana.com/2021/10/20211002145412980o.html

  1. 初学者怎么学Web前端?
  2. react
  3. PaddlePaddle:在 Serverless 架构上十几行代码实现 OCR 能力
  4. JavaScript数组 几个常用方法
  5. Angular 依赖注入 - 全面解析
  6. html_day02
  7. 那些年我们前端面试中经常被问到的题!
  8. The starting price of Ducati multistada V2 in North America is less than 100000 yuan
  9. Hls.js 使用文檔
  10. Hls.js travailler avec des documents
  11. Problèmes liés à la précision JS
  12. Copie une partie des propriétés d'un objet à un autre objet
  13. Multiplexage de modules en vuex
  14. Développement multilingue Android, questions d'entrevue pour le développement de logiciels Android
  15. Chen lushai and her best friend Wang Meng play video, fearless of the pressure of public opinion, and in a good mood to dance in a bare back
  16. # Sass速通(四):继承、混合与函数
  17. Vidéo de développement de combat Android, questions d'entrevue rxjava
  18. Bugatti Chiron maintenance cost exposure! One piece for one car, burn money endlessly
  19. android应用开发基础答案,深入理解Nginx
  20. 做了三年前端,你才知道10分钟就能实现一个PC版魔方游戏
  21. Html + CSS + JS implémentation ️ Responsive Lucky Turnover ️ [with full source Sharing]
  22. Ren Jialun, who married young, was in a mess. Now she feels that it is a blessing in disguise
  23. 达梦数据库使用disql生成html格式的巡检报告
  24. React render phase parsing II - beginwork process
  25. Tableau linéaire de la structure des données (dessin à la main)
  26. In 2022, what are the highlights and popular elements in skirts to make skirts more elegant and gentle?
  27. JQuery installation
  28. Exemple de développement Android, dernière compilation de questions d'entrevue Android
  29. Differences and relations between JDK, JRE and JVM, nginx architecture diagram
  30. 【Azure 云服务】Azure Cloud Service 为 Web Role(IIS Host)增加自定义字段 (把HTTP Request Header中的User-Agent字段增加到IIS输出日志中)
  31. 【Azure 云服务】Azure Cloud Service 为 Web Role(IIS Host)增加自定义字段 (把HTTP Request Header中的User-Agent字段增加到IIS输出日志中)
  32. Questions d'entrevue pour les ingénieurs en développement Android, Android Foundation 72 questions
  33. It's kind of Cadillac CT6 to have a Mercedes Benz S-class captain and a 10At entry-level configuration, falling to less than 300000
  34. H6 meets the strong enemy again! The car body has a Cayenne visual sense, breaking 8.8 seconds, and the top configuration is less than 130000
  35. How nginx supports HTTPS and Linux kernel video tutorial
  36. Le martyr se réjouit de sa vieillesse Audi R8 V10 performance Rwd
  37. import 方式隨意互轉,感受 babel 插件的威力
  38. Le mode d'importation peut se déplacer librement pour sentir la puissance du plug - in Babel
  39. Pas de héros en termes de ventes!Du point de vue de la force du produit, la nouvelle version ax7 Mach est plus forte que H6
  40. The vue3 + TS project introduces vant as needed
  41. 深入浅出虚拟 DOM 和 Diff 算法,及 Vue2 与 Vue3 中的区别
  42. 深入淺出虛擬 DOM 和 Diff 算法,及 Vue2 與 Vue3 中的區別
  43. Explorer les algorithmes DOM et diff virtuels et les différences entre vue2 et vue3
  44. 两万字Vue基础知识总结,小白零基础入门,跟着路线走,不迷路(建议收藏)
  45. Résumé des connaissances de base de 20 000 mots vue, Introduction à la petite base blanche zéro, suivre la route et ne pas se perdre (Collection recommandée)
  46. 兩萬字Vue基礎知識總結,小白零基礎入門,跟著路線走,不迷路(建議收藏)
  47. "Talk show conference 4" Zhou qimo a remporté le championnat. Tout le monde l'admire. Il est mature et stable et a une vue d'ensemble
  48. Test logiciel entrevue non technique questions classiques - mise à jour continue!
  49. Digital forward disassembly reverse disassembly
  50. Analyse du cache distribué redis et essence de l'entrevue en usine v6.2.6
  51. [Hadoop 3. X series] use of HDFS rest HTTP API (II) httpfs
  52. Zhang Daxian sang in the morning to bless the motherland, xYG team: singing is much better than us
  53. My three years' experience -- avoiding endless internal friction
  54. Introduction à l'algorithme "dénombrement binaire" modéré 01 - - question d'entrevue leetcode 10.09. Recherche de matrice de tri
  55. Introduction à l'algorithme simple 06 - - leetcode 34. Trouver la première et la dernière position d'un élément dans un tableau de tri
  56. CSS animation
  57. Explain the new tags in HTML5 and the pseudo classes and pseudo elements in CSS3
  58. They are all talking about "serverless first", but do you really understand serverless?
  59. [apprentissage de l'algorithme] 1486. Fonctionnement exclusif du tableau (Java / C / C + + / python / go / Rust)
  60. Front and back end data interaction (VI) -- advantages, disadvantages and comparison of Ajax, fetch and Axios