java 反转链表、合并链表
生活随笔
收集整理的這篇文章主要介紹了
java 反转链表、合并链表
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
第一個問題:反轉鏈表
1. 題目描述
輸入一個鏈表,反轉鏈表后,輸出新鏈表的表頭。
2. 解題思路
定義三個指針:
第一個指針指向當前正在處理的節點;
第二個指針指向當前處理節點的下一個節點,該指針是為了保證正常的遍歷完順序鏈表的所有節點;
第三個指針指向當前處理節點的上一個節點,這里主要是為了修改當前指針的指向,也就是指向反向;
3. 代碼
class ListNode {int val;ListNode next = null;public ListNode(int val) {this.val = val;} }public class ReverseList {public static void main(String[] args) {// 定義節點ListNode root = new ListNode(0) ;ListNode n1 = new ListNode(3) ;ListNode n2 = new ListNode(5) ;ListNode n3 = new ListNode(6) ;ListNode n4 = new ListNode(7) ;ListNode n5 = new ListNode(9) ;// 連接節點root.next=n1;n1.next=n2;n2.next=n3;n3.next=n4;n4.next=n5;ListNode tmpnode=root;while(tmpnode!=null) {System.out.print(tmpnode.val);tmpnode=tmpnode.next;}System.out.println();ListNode nodenew= RevList(root);while(nodenew!=null) {System.out.print(nodenew.val);nodenew=nodenew.next;}}public static ListNode RevList(ListNode head) {ListNode newhead=null; ListNode prenode=null;ListNode current=head;ListNode nextnode=null;while(current!=null) { nextnode=current.next; if(nextnode==null) {newhead=current;} current.next=prenode; prenode=current;current=nextnode;} return newhead;}}運行結果:
035679 976530第二個問題:合并兩個排序的鏈表
1. 題目描述
輸入兩個單調遞增的鏈表,輸出兩個鏈表合成后的鏈表,當然我們需要合成后的鏈表滿足單調不減規則。
2. 解題思路
非遞歸:首先新建一個頭節點用來存儲新的合并的鏈表,然后依次比較兩個鏈表的各個節點的值大小,排序。類似于“按大小把數值一個個串起來作為新的鏈表”
遞歸:和上述非遞歸的值比較方法一致,只不過用的是遞歸的方法。
3. 代碼:
非遞歸代碼一:
class ListNode {int val;ListNode next = null;public ListNode(int val) {this.val = val;} }public class Merge {public static void main(String[] args) {// 定義節點ListNode root1 = new ListNode(0) ;ListNode n11 = new ListNode(1) ;ListNode n12 = new ListNode(3) ;ListNode n13= new ListNode(5) ;ListNode n14 = new ListNode(7) ;ListNode n15 = new ListNode(16) ;// 連接節點root1.next=n11;n11.next=n12;n12.next=n13;n13.next=n14;n14.next=n15;// 定義節點ListNode root2 = new ListNode(0) ;ListNode n21 = new ListNode(5) ;ListNode n22 = new ListNode(9) ;ListNode n23 = new ListNode(10) ;ListNode n24 = new ListNode(12) ;ListNode n25 = new ListNode(14) ;// 連接節點root2.next=n21;n21.next=n22;n22.next=n23;n23.next=n24;n24.next=n25;ListNode tmpnode1=root1;while(tmpnode1!=null) { System.out.print(String.valueOf(tmpnode1.val)+','); tmpnode1=tmpnode1.next;}System.out.println(); ListNode tmpnode2=root2;while(tmpnode2!=null) {System.out.print(String.valueOf(tmpnode2.val)+',');tmpnode2=tmpnode2.next;}System.out.println('\n');ListNode newhead=Mer(root1,root2);System.out.println('\n'); ListNode tmpnode3=newhead; while(tmpnode3!=null) {System.out.print(String.valueOf(tmpnode3.val)+',');tmpnode3=tmpnode3.next;}}public static ListNode Mer(ListNode list1,ListNode list2) {if(list1==null) {return list2;}else if(list2==null){return list1;}ListNode mergehead=new ListNode(-1);ListNode root=mergehead;while(list1!=null && list2!=null) {if(list1.val<=list2.val) {mergehead.next=list1;System.out.println("h1:"+String.valueOf(mergehead.next.val));mergehead=list1;list1=list1.next; }else { mergehead.next=list2; System.out.println("h2:"+String.valueOf(mergehead.next.val));mergehead=list2;list2=list2.next;}}if(list1!=null){mergehead.next=list1;}if(list2!=null){mergehead.next=list2;}return root.next;}}運行:
0,1,3,5,7,16, 0,5,9,10,12,14,h1:0 h2:0 h1:1 h1:3 h1:5 h2:5 h1:7 h2:9 h2:10 h2:12 h2:140,0,1,3,5,5,7,9,10,12,14,16,非遞歸代碼二:
class ListNode {int val;ListNode next = null;public ListNode(int val) {this.val = val;} }public class Merge {public static void main(String[] args) {// 定義節點ListNode root1 = new ListNode(0) ;ListNode n11 = new ListNode(1) ;ListNode n12 = new ListNode(3) ;ListNode n13= new ListNode(5) ;ListNode n14 = new ListNode(7) ;ListNode n15 = new ListNode(16) ;// 連接節點root1.next=n11;n11.next=n12;n12.next=n13;n13.next=n14;n14.next=n15;// 定義節點ListNode root2 = new ListNode(0) ;ListNode n21 = new ListNode(5) ;ListNode n22 = new ListNode(9) ;ListNode n23 = new ListNode(10) ;ListNode n24 = new ListNode(12) ;ListNode n25 = new ListNode(14) ;// 連接節點root2.next=n21;n21.next=n22;n22.next=n23;n23.next=n24;n24.next=n25;ListNode tmpnode1=root1;while(tmpnode1!=null) { System.out.print(String.valueOf(tmpnode1.val)+','); tmpnode1=tmpnode1.next;}System.out.println(); ListNode tmpnode2=root2;while(tmpnode2!=null) {System.out.print(String.valueOf(tmpnode2.val)+',');tmpnode2=tmpnode2.next;}System.out.println('\n');ListNode newhead=Mer(root1,root2);System.out.println('\n'); ListNode tmpnode3=newhead; while(tmpnode3!=null) {System.out.print(String.valueOf(tmpnode3.val)+',');tmpnode3=tmpnode3.next;}}public static ListNode Mer(ListNode list1,ListNode list2) {if(list1==null) {return list2;}else if(list2==null){return list1;}ListNode mergeHead = null;ListNode current = null; while(list1!=null && list2!=null){if(list1.val <= list2.val){if(mergeHead == null){mergeHead = current = list1;}else{current.next = list1;current = current.next;}list1 = list1.next; }else {if(mergeHead == null){mergeHead = current = list2;}else{current.next = list2;current = current.next;}list2 = list2.next;}}if(list1 == null){current.next = list2;}else{current.next = list1;}return mergeHead;} }運行:
0,1,3,5,7,16, 0,5,9,10,12,14,0,0,1,3,5,5,7,9,10,12,14,16,遞歸代碼:
public ListNode Mer(ListNode list1,ListNode list2) {if(list1 == null){return list2;}if(list2 == null){return list1;}if(list1.val <= list2.val){list1.next = Merge(list1.next, list2);return list1;}else{list2.next = Merge(list1, list2.next);return list2;} }這樣看來還是遞歸厲害,但基本思路還是上述的非遞歸中的思想。
僅作為自己學習的筆記。。
總結
以上是生活随笔為你收集整理的java 反转链表、合并链表的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: java 调整数组顺序使奇数位于偶数前面
- 下一篇: 炙黄芪(炙)