[Java data structure] you must master the classic example of linked list interview (with super detailed illustration and code)

/Shao Siming 2021-11-25 17:57:32
java data structure master classic

Catalog

One , Write it at the front

Two , Classic examples of linked lists

1, Invert a single chain table

2, Given a node with a header head The non empty single chain table of , Returns the middle node of the linked list

3, Enter a linked list , Output the last number in the list k Nodes

4, Delete multiple duplicate values in the linked list

5, Palindrome structure of linked list

6, Merge two linked lists

7, Enter two linked lists , Find their first common node .

8, Judge whether a linked list has links

9, Find the first node of a ring with a linked list


One , Write it at the front

Linked list is almost the top priority of data structure , The linked list is also a necessary knowledge point for the interview of large factories , To learn the linked list well , The most important thing is to draw pictures to solve problems , If you think this blog is good , seek give the thumbs-up , For collection , Ask for comment , Your third company is the biggest driving force for my progress , I don't say much nonsense , Let's learn !!!

Two , Classic examples of linked lists

1, Invert a single chain table

 

public ListNode reverseList() {
if(this.head == null) {
return null;
}
ListNode cur = this.head;
ListNode prev = null;
while (cur != null) {
ListNode curNext = cur.next;
cur.next = prev;
prev = cur;
cur = curNext;
}
return prev;
}

 2, Given a node with a header head The non empty single chain table of , Returns the middle node of the linked list

public ListNode middleNode() {
if(head == null) {
return null;
}
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null){
fast = fast.next.next;
if(fast == null) {
return slow;
}
slow = slow.next;
}
return slow;
}

 3, Enter a linked list , Output the last number in the list k Nodes

 public ListNode findKthToTail(int k) {
if(k <= 0 || head == null) {
return null;
}
ListNode fast = head;
ListNode slow = head;
while (k-1 != 0) {
fast = fast.next;
if(fast == null) {
return null;
}
k--;
}
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
return slow;
}

4, Delete multiple duplicate values in the linked list

// Delete all values as key The node of
public ListNode removeAllKey(int key){
if(this.head == null) return null;
ListNode prev = this.head;
ListNode cur = this.head.next;
while (cur != null) {
if(cur.val == key) {
prev.next = cur.next;
cur = cur.next;
}else {
prev = cur;
cur = cur.next;
}
}
// Final processing head
if(this.head.val == key) {
this.head = this.head.next;
}
return this.head;
}

5, Palindrome structure of linked list

 public boolean chkPalindrome(ListNode A) {
// write code here
if(head == null) return true;
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
//slow Come to the middle -》 reverse
ListNode cur = slow.next;
while(cur != null) {
ListNode curNext = cur.next;
cur.next = slow;
slow = cur;
cur = curNext;
}
// Reverse complete
while(head != slow) {
if(head.val != slow.val) {
return false;
}
if(head.next == slow) {
return true;
}
head = head.next;
slow = slow.next;
}
return true;
}

6, Merge two linked lists

public static ListNode mergeTwoLists(ListNode headA, ListNode headB) {
ListNode newHead = new ListNode(-1);
ListNode tmp = newHead;
while (headA != null && headB != null) {
if(headA.val < headB.val) {
tmp.next = headA;
headA = headA.next;
tmp = tmp.next;
}else {
tmp.next = headB;
headB = headB.next;
tmp = tmp.next;
}
}
if(headA != null) {
tmp.next = headA;
}
if(headB != null) {
tmp.next = headB;
}
return newHead.next;
}

7, Enter two linked lists , Find their first common node .

 public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA == null || headB == null) {
return null;
}
ListNode pl = headA;
ListNode ps = headB;
int lenA = 0;
int lenB = 0;
while (pl != null) {
lenA++;
pl = pl.next;
}
//pl==null
pl = headA;
while (ps != null) {
lenB++;
ps = ps.next;
}
//ps==null
ps = headB;
int len = lenA-lenB;// Step two
if(len < 0) {
pl = headB;
ps = headA;
len = lenB-lenA;
}
//1、pl It always points to the longest linked list ps Always point to the shortest linked list 2、 I got the difference len Step
//pl Walk difference len Step
while (len != 0) {
pl = pl.next;
len--;
}
// Go at the same time Until we met
while (pl != ps) {
pl = pl.next;
ps = ps.next;
}
return pl;
}

8, Judge whether a linked list has links

 public boolean hasCycle() {
if(head == null) return false;
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if(fast == slow) {
return true;
}
}
return false;
}

 9, Find the first node of a ring with a linked list

 public ListNode detectCycle(ListNode head) {
if(head == null) return null;
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if(fast == slow) {
break;
}
}
if(fast == null || fast.next == null) {
return null;
}
fast = head;
while (fast != slow) {
fast = fast.next;
slow = slow.next;
}
return fast;
}

 

版权声明
本文为[/Shao Siming]所创,转载请带上原文链接,感谢
https://javamana.com/2021/11/20211109094540359a.html

  1. 6年老猿带你掌握Spring Boot实现定时任务的动态增删启停
  2. disruptor笔记之六:常见场景,java教程从入门到精通pdf百度云
  3. Pourquoi InnoDB n'utilise - t - il pas un cache LRU naïf?
  4. Java Reflection (2): quelques opérations de base de reflection
  5. 6年老猿帶你掌握Spring Boot實現定時任務的動態增删啟停
  6. Les singes âgés vous permettent de maîtriser le démarrage et l'arrêt dynamiques des tâches programmées par Spring boot
  7. Docker From Beginning to Practice Series IV - docker Container chorégraphe Clean docker Composition
  8. 编写 java 程序,为家用电脑 ipv6 自动更新 goddy dns 记录(ddns)
  9. java jvm-old gc耗时几十s,导致系统告警
  10. Disruptor note 6: scénario commun, tutoriel Java de l'introduction à la maîtrise du PDF Baidu Cloud
  11. 编写Java程序启动脚本最佳实践
  12. How to get the correct Linux user's documents, music videos and other directories?
  13. Java JVM Old GC prend des dizaines de s, ce qui provoque une alarme système
  14. Écrivez un programme Java pour mettre à jour automatiquement les enregistrements DNS goddy (ddns) pour l'ordinateur domestique IPv6
  15. 編寫Java程序啟動脚本最佳實踐
  16. Meilleures pratiques pour écrire des scripts de démarrage de programmes Java
  17. Notes sur springcloud Eureka
  18. Ajout, suppression et modification simples de mybatis
  19. MySQL Learning - Logging System Redo log and Bin log
  20. Springboot Common comments | @ configuration
  21. Mécanisme d'expiration du cache redis et d'élimination de la mémoire
  22. Analyse concise du code source redis 01 - configuration de l'environnement
  23. Java - carte mémoire de l'objet
  24. Redis source Concise Analysis 02 - SDS String
  25. Why did docker lose to kubernetes? Docker employee readme!
  26. Spring cloud gateway practice 2: more routing configuration methods
  27. Principe de mise en œuvre ultime du mécanisme de concurrence Java sous - jacent
  28. [démarrer avec Java 100 exemples] 13. Modifier l’extension de fichier - remplacement de chaîne
  29. Java期末作业——王者荣耀的洛克王国版游戏
  30. Elasticsearch聚合学习之五:排序结果不准的问题分析,阿里巴巴java性能调优实战
  31. Java期末作業——王者榮耀的洛克王國版遊戲
  32. Java final work - King's Glory Rock Kingdom Game
  33. 【网络编程】TCP 网络应用程序开发
  34. 【网络编程入门】什么是 IP、端口、TCP、Socket?
  35. 【網絡編程入門】什麼是 IP、端口、TCP、Socket?
  36. [Introduction à la programmation réseau] qu'est - ce que IP, port, TCP et socket?
  37. [programmation réseau] développement d'applications réseau TCP
  38. [Java Basics] comprendre les génériques
  39. Dix outils open source que les architectes de logiciels Java devraient maîtriser!!
  40. Java经典面试题详解,突围金九银十面试季(附详细答案,mysql集群架构部署方案
  41. java架构之路(多线程)synchronized详解以及锁的膨胀升级过程,mysql数据库实用教程pdf
  42. java整理,java高级特性编程及实战第一章
  43. java教程——反射,mongodb下载教程
  44. Java岗大厂面试百日冲刺 - 日积月累,每日三题【Day12,zookeeper原理作用
  45. Java后端互联网500道中高级面试题(含答案),linux钩子技术
  46. java8 Stream API及常用方法,java初级程序员面试
  47. java-集合-Map(双列)——迪迦重制版,2021Java开发社招面试解答之性能优化
  48. Flink处理函数实战之二:ProcessFunction类,java线程面试题目
  49. flex 布局详解,【Java面试题
  50. Linux basic command learning
  51. Why did docker lose to kubernetes? Docker employee readme!
  52. MySQL安装
  53. Elastic Search Aggregate Learning five: Problem Analysis of Uncertainty of sequencing results, Alibaba Java Performance Tuning Practical
  54. Installing, configuring, starting and accessing rabbitmq under Linux
  55. Oracle SQL injection summary
  56. Installation MySQL
  57. L'exposition à la photo d'essai sur la route i7 du nouveau vaisseau amiral de BMW Pure Electric a également été comparée à celle de Xiaopeng p7.
  58. spring JTA 关于异常处理的时机问题
  59. Le problème du temps de traitement des exceptions dans la JTA printanière
  60. Do you really know MySQL order by