数据结构与算法之链表

时间:2021-09-07 09:47:41

  链表这种数据结构,真的比较难以掌握的,感觉有点头疼。。。和数组相比,链表更适合插入。删除操作频繁的场景,查询的时间复杂度较高

一、链表种类

数据结构与算法之链表

单链表、循环链表、双向链表

数据结构与算法之链表

数据结构与算法之链表

数据结构与算法之链表

二、链表中常用的算法练习

 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 }