数据结构_单链表操作总结

  1 package zz;
  2 
  3 import java.util.Stack;
  4 
  5 /**
  6  * 
  7  * @author zz
  8  * 关于java中链表的操作
  9  * 0. 向链表中插入新节点
 10  * 1. 求单链表中结点的个数: getListLength 
 11  * 2. 将单链表反转: reverseList（遍历），reverseListRec（递归） 
 12  * 3. 查找单链表中的倒数第K个结点（k > 0）: reGetKthNode 
 13  * 4. 查找单链表的中间结点: getMiddleNode 
 14  * 5. 从尾到头打印单链表: reversePrintListStack，reversePrintListRec（递归） 
 15  * 6. 已知两个单链表pHead1 和pHead2 各自有序，把它们合并成一个链表依然有序: mergeSortedList, mergeSortedListRec 
 16  * 7. 对链表的后半部分进行反转。reversePartNode
 17  * 8. 判断单链表是否存在环，isLoop。 使用两个指针，fast和low，fast一次走两步，low一次走一步。若存在环，总会有某个时刻fast和low指向同一节点
 18  * 9. 求出环的长度。getLoopLength().记录8中fast和low的遭遇点。然后让low走一圈环记数即可
 19  * 10. 对单链表进行排序,listSort（归并）,insertionSortList（插入）
 20  * // 注释部分代码也经过调试正确
 21  */
 22 public class LinkedListSummary {
 23     public static class Node {
 24         int data;
 25         Node next;
 26         public Node(int value) {
 27             data = value;
 28             next = null;
 29         }
 30     }
 31     //向链表中插入新节点
 32     public static void addNode(Node head, int data) {
 33         Node newNode = new Node(data);
 34         if(head == null) {
 35             head = newNode;
 36             return;
 37         } else {
 38             Node temp = head;
 39             while(temp.next != null) {
 40                 temp = temp.next;
 41             }
 42             temp.next = newNode;            
 43         }
 44     }
 45     //输出链表的长度
 46     public static int getListLength(Node head) {
 47         int len = 0;
 48         //if(head == null) return 0;
 49         Node temp = head;
 50         while(temp != null) {
 51             len++;
 52             temp = temp.next;
 53         }
 54         System.out.println("输出链表长度：" + len);
 55         return len;
 56     }    
 57     //顺序打印链表数据 
 58     public static void print(Node head) {
 59        if(head == null) {
 60            System.out.println("链表为空");
 61            return;
 62        }
 63        Node temp = head;
 64        while(temp != null) {
 65            System.out.print(temp.data + " ");
 66            temp = temp.next;
 67        }
 68     }
 69     //方法1：使用栈反向遍历单链表
 70     public static void reversePrint(Node head) {
 71         if(head == null || head.next == null) return;
 72         Stack<Node> nodes = new Stack<Node>();
 73         Node temp = head;
 74         while(temp != null) {
 75             nodes.push(temp);
 76             temp = temp.next;
 77         }
 78         while(!nodes.isEmpty()) {
 79             //nodes.pop();
 80             System.out.print(nodes.pop().data + " ");
 81         }
 82     }
 83     //方法二：反向遍历单链表
 84     public static Node reversePrint2(Node head) {
 85         if(head == null || head.next == null) return head;
 86         Node pre = null;
 87         Node temp = null;
 88         while(head != null) {
 89             temp = head.next;
 90             head.next = pre;
 91             pre = head;
 92             head = temp;
 93         } 
 94         print(pre);
 95     //    System.out.println(head == null ? "空" : "非空");
 96         return pre;
 97     }    
 98     //递归反向遍历单链表
 99     public static Node reversePrintRec(Node head) {
100         if(head == null || head.next == null) {
101             System.out.println("链表遍历完成，只有head节点或为空链表");
102             return head;
103         }
104         Node reHead = reversePrintRec(head.next);
105          head.next.next = head;
106         head.next = null;
107         return head;
108     }
109     //从尾到头打印递归打印单链表
110     public static void reversePrintListRec(Node head) {
111         if(head == null) {
112             return;
113         } else {
114             reversePrintListRec(head.next);
115             System.out.print(head.data + ",");
116         }
117     }
118     //查找单链表的倒数第K个节点（k>0）
119     public static Node reGetKthNode(Node head, int k) {
120         int len = 0;
121         Node temp = head;
122         while(temp != null) {
123             len++;
124             temp = temp.next;
125         }
126         if(k > len) {
127             System.out.println("链表长度有限，小于K，找不到倒数第K个节点");
128             return null;
129         }
130         Node n1 = head;
131         Node n2 = head;
132         for(int i = 0; i < k; i++) {
133             n1 = n1.next;
134         }
135         while(n1 != null){
136             n2 = n2.next;
137             n1 = n1.next;
138         }
139         System.out.println(n2.data);
140         return n2;
141     }
142     //查找单链表的中间结点: getMiddleNode
143     public static Node getMiddleNode(Node head) {
144         if(head == null || head.next == null) return head;
145         Node n1 = head;
146         Node n2 = head;
147         while(n2 != null && n2.next != null) {
148             n1 = n1.next;
149             n2 = n2.next.next;
150         }
151         //System.out.println(n1.data);
152         return n1;
153     }
154     //已知两个单链表pHead1 和pHead2 各自有序，把它们合并成一个链表依然有序: mergeSortedList
155     public static Node mergeSortedList(Node head1, Node head2) {
156         if(head1 == null) return head2;
157         if(head2 == null) return head1;
158         Node target = null;
159         if(head1.data > head2.data) {
160             target = head2;
161             head2 = head2.next;
162         } else {
163             target = head1;
164             head1 = head1.next;
165         } 
166         target.next = null;
167         Node newHead = target;
168         while(head1 != null && head2 != null) {
169             if(head1.data > head2.data) {
170                 target.next = head2;
171                 head2 = head2.next;
172             } else {
173                 target.next = head1;
174                 head1 = head1.next;
175             }
176             target = target.next;
177             target.next = null;
178         }
179         if(head1 == null) {
180             target.next = head2;
181         } else {
182             target.next = head1; 
183         }
184         return newHead;
185     }
186     //已知两个单链表pHead1 和pHead2 各自有序，把它们合并成一个链表依然有序(递归实现): mergeSortedListRec
187     public static Node mergeSortedListRec(Node head1, Node head2) {
188         if(head1 == null) return head2;
189         if(head2 == null) return head1;
190         Node head = null;
191         if(head1.data > head2.data) {
192             head = head2;
193             head.next = mergeSortedListRec(head2.next, head1);
194         } else {
195             head = head1;
196             head.next = mergeSortedListRec(head1.next, head2);
197         }
198          return head;
199     }
200     //将链表的后半部分进行反转
201     public static Node reversePartNode(Node head){  
202         Node flag = head;
203         Node cur = null;
204         Node mid = getMiddleNode(head);
205         
206         while(flag.next != mid) {     //取出中间节点的 前一个节点并保存
207             flag = flag.next;
208         }
209         Node pre = null;
210         //System.out.println("----" + flag.data);
211         while(mid != null) {
212             cur = mid.next;
213             mid.next = pre; 
214             pre = mid;
215             mid = cur;
216         } 
217        
218         flag.next = pre;
219         print(head);
220 
221         return head;
222     }  
223     //判断链表是否存在环
224     public static boolean isLoop(Node head) {
225         if(head == null || head.next != null) return false;
226         Node fast = head;
227         Node low = head;
228         while(fast != null && fast.next != null) {
229             low = low.next;
230             fast = fast.next.next;
231             if(fast == low) break;
232         }
233         if(fast == null || fast.next == null) return false;
234         return true;
235     }
236     //求出环的长度
237     public static int getLoopLength(Node head) {
238         if(head == null || head.next != null) return 0;
239         Node fast = head;
240         Node low = head;
241         while(fast != null && fast.next != null) {
242             low = low.next;
243             fast = fast.next.next;
244             if(fast == low) break;
245         }
246         if(fast == null || fast.next == null) return 0;
247         else {
248             int loopLen = 1;
249             while(low.next != fast) {
250                 loopLen++;
251                 low = low.next;
252             }
253             return loopLen;
254         }
255         
256     }
257 /*  
258     //单链表排序
259     public static Node listSort(Node head) {
260         Node nex = null;
261         if(head == null || head.next == null) return head;
262         else if(head.next.next == null) {
263             nex = head.next;
264             head.next = null;
265         } else {
266             Node mid = getMiddleNode(head);
267             nex = mid.next;
268             mid.next = null;
269         }
270         print(mergeSortedList(listSort(head), listSort(nex)));
271         return mergeSortedList(listSort(head), listSort(nex));
272     }
273 */
274     public static void main(String[] args) {
275         Node head = new Node(0);
276         addNode(head, 6);
277         addNode(head, 2);
278         addNode(head, 1);
279         addNode(head, 4);
280         addNode(head, 3);
281         addNode(head, 5);
282     //    listSort(head);
283         System.out.println("顺序打印链表数据：");
284         print(head);
285         System.out.println();
286         System.out.println("反转单链表后半部分节点：");
287         reversePartNode(head);
288         System.out.println();
289         
290         if(isLoop(head)) {
291             System.out.println("存在环");
292         } else System.out.println("不存在环");
293         
294         Node head1 = new Node(10);
295         addNode(head1, 11);
296         addNode(head1, 12);
297         addNode(head1, 13);
298         addNode(head1, 14);
299         addNode(head1, 15);
300         addNode(head1, 16);
301         addNode(head1, 17);
302         addNode(head1, 18);
303         addNode(head1, 19);
304         addNode(head1, 20);
305         /*
306         System.out.println();
307         System.out.println("反转单链表后半部分节点：");
308         reversePartNode(head1);
309         System.out.println();
310         */
311         Node head2 = new Node(100);
312         for(int i = 0; i < 8; i++) {
313             addNode(head2, 100+i);
314         }
315         
316         Node head3 = new Node(1000);
317         for(int i = 0; i < 8; i++) {
318             addNode(head3, 1001+i);
319         }
320         
321         getListLength(head);
322         System.out.println("顺序打印链表数据：");
323         print(head);
324     /*
325     //    System.out.println();
326     //    System.out.println("使用栈反转链表:");
327     //    reversePrint(head);
328     //    System.out.println();
329     //    reversePrint2(head);
330     //    System.out.println();
331     //    System.out.println("递归反向遍历单链表");
332     //    System.out.println("----" + head.data);
333     //    reversePrintListRec(head);
334     //    System.out.println();
335     //    System.out.println("查找单链表的倒数第K个节点的值");
336     //    reGetKthNode(head, 3);
337     //    System.out.println();
338     //    System.out.println("查找单链表的中间节点的值");
339     //    getMiddleNode(head);
340     //    System.out.println();
341     //    System.out.println("合并两个单链表：");
342     //    Node mergeHead = mergeSortedList(head, head1);
343     //    print(mergeHead);
344     //    System.out.println();
345     //    System.out.println("递归实现合并两个单链表：");
346     //    Node mergeHeadRec = mergeSortedListRec(head2, head3);
347     //    print(mergeHeadRec);
348         */
349     } 
350 }