链表这种数据结构，真的比较难以掌握的，感觉有点头疼。。。和数组相比，链表更适合插入。删除操作频繁的场景，查询的时间复杂度较高
一、链表种类
单链表、循环链表、双向链表
二、链表中常用的算法练习
1 /** 2 * 节点的实体类 3 * 4 * @author ssc 5 * @date 2019.03.05 6 */ 7 public class Node { 8 9 public int value; 10 public Node next; 11 12 public Node(){ 13 super(); 14 } 15 16 public Node(int data) { 17 this.value = data; 18 } 19 }
1 /*** 2 * 链表结构中常用的 3 * 4 * @author ssc 5 * @date 2019.03.05 6 */ 7 public class Reverse { 8 9 /** 10 * 遍历法链表反转 11 * 12 * @return 13 */ 14 public static Node reverse1(Node list) { 15 Node headNode = null; 16 Node previousNode = null; 17 Node currentNode = list; 18 19 while (currentNode != null) { 20 Node nextNode = currentNode.next; 21 if (nextNode == null) { 22 headNode = currentNode; 23 } 24 currentNode.next = previousNode; 25 previousNode = currentNode; 26 currentNode = nextNode; 27 } 28 return headNode; 29 } 30 31 /** 32 * 链表中环的检测 33 * 34 * @return 35 */ 36 public static boolean checkCircle(Node list) { 37 if (list == null) { 38 return false; 39 } 40 Node fast = list.next; 41 Node slow = list; 42 43 if (fast != null && fast.next != null) { 44 fast = fast.next.next; 45 slow = slow.next; 46 if (fast == slow) { 47 return true; 48 } 49 } 50 return false; 51 } 52 53 /** 54 * 两个有序链表合并 55 * 56 * @param la 57 * 有序链表a 58 * @param lb 59 * 有序链表b 60 * @return 61 */ 62 public static Node mergeSortedLists(Node la, Node lb) { 63 64 if (la == null) { 65 return lb; 66 } 67 if (lb == null) { 68 return la; 69 } 70 Node p = la; 71 Node q = lb; 72 Node head; 73 if (p.value < q.value) { 74 head = p; 75 p = p.next; 76 } else { 77 head = q; 78 q = q.next; 79 } 80 Node r = head; 81 82 while (p != null && q != null) { 83 if (p.value < q.value) { 84 r.next = p; 85 p.next = p; 86 } else { 87 r.next = q; 88 q.next = q; 89 } 90 r = r.next; 91 } 92 93 if (p != null) { 94 r.next = p; 95 } else { 96 r.next = q; 97 } 98 return head; 99 } 100 101 /** 102 * 删除倒数第k个结点 103 * 104 * @param list 链表 105 * @param k 106 * @return 107 */ 108 public static Node deleteLastKth(Node list, int k) { 109 110 Node fast = list; 111 112 int i = 1; // k=2 113 while (fast != null && i < k) { 114 fast = fast.next; // 2,3 115 ++i; 116 } 117 118 if(fast == null){ 119 return list; 120 } 121 Node slow = list; // 1,2,3 122 Node prev = null; 123 124 while(fast.next != null){ 125 fast = fast.next; // 3 126 prev = slow; // 1,2,3 127 slow = slow.next; // 2,3 128 } 129 if(prev == null){ 130 list = list.next; 131 }else{ 132 prev.next = prev.next.next; 133 printAll(prev); 134 } 135 return list; 136 } 137 138 /** 139 * 求中间结点 140 * 141 * @param list 142 * @return 143 */ 144 public static Node findMiddleNode(Node list){ 145 if(list == null){ 146 return null; 147 } 148 149 Node fast = list; 150 Node slow = list; 151 152 while(fast.next != null && fast.next.next != null){ 153 fast = fast.next.next; 154 slow = slow.next; 155 } 156 return slow; 157 } 158 159 /** 160 * 打印链表中存储的数值 161 * 162 * @param list 163 */ 164 public static void printAll(Node list) { 165 while (list != null) { 166 System.out.print(list.value + " "); 167 list = list.next; 168 } 169 System.out.println(); 170 } 171 }
此大部分内容来自极客时间专栏，王争老师的《数据结构与算法之美》