合并兩個已經排序好的鏈表

2019-11-08 02:28:20

字體：大中小

來源：轉載

供稿：網友

一，問題描述 1，輸入兩個單調遞增的鏈表，輸出兩個鏈表合成后的鏈表。新鏈表也是單調遞增的。

二，程序如下(java實現）：

1，非遞歸合并有序鏈表

import java.util.*;class ListNode{ int val; ListNode next; ListNode(int x) { val=x; }}public class Test{ public ListNode Merge(ListNode node1,ListNode node2) { if(node1==null&&node2==null) { return null; } if(node1==null) { return node2; } if(node2==null) { return node1; } ListNode node3=null; //這個作為偏移指針 ListNode node4=null; //這個作為頭指針 while(node1!=null&&node2!=null) { if(node1.val<=node2.val) { if(node4==null) { node3=node1; node4=node1; } else { node3.next=node1; node3=node3.next; } node1=node1.next; } else { if(node4==null) { node3=node2; node4=node2; } else { node3.next=node2; node3=node3.next; } node2=node2.next; } } if(node1!=null) { node3.next=node1; } if(node2!=null) { node3.next=node2; } return node4; } public static void main(String []args) { Test test=new Test(); ListNode node11=new ListNode(1); ListNode node12=new ListNode(3); ListNode node13=new ListNode(5); ListNode node14=new ListNode(7); ListNode node15=new ListNode(9); ListNode node21=new ListNode(2); ListNode node22=new ListNode(4); ListNode node23=new ListNode(6); ListNode node24=new ListNode(8); ListNode node25=new ListNode(10); node11.next=node12; node12.next=node13; node13.next=node14; node14.next=node15; node21.next=node22; node22.next=node23; node23.next=node24; node24.next=node25; ListNode node=test.Merge(node11,node22); while(node!=null) { System.out.2，遞歸方式合并有序鏈表

import java.util.*;class ListNode{ int val; ListNode next; ListNode(int x) { val=x; }}public class Test{ public ListNode Merge(ListNode node1,ListNode node2) { if(node1==null) { return node2; } if(node2==null) { return node1; } if(node1.val<=node2.val) { node1.next=Merge(node1.next,node2); return node1; } else { node2.next=Merge(node1,node2.next); return node2; } } public static void main(String []args) { Test test=new Test(); ListNode node11=new ListNode(1); ListNode node12=new ListNode(3); ListNode node13=new ListNode(5); ListNode node14=new ListNode(7); ListNode node15=new ListNode(9); ListNode node21=new ListNode(2); ListNode node22=new ListNode(4); ListNode node23=new ListNode(6); ListNode node24=new ListNode(8); ListNode node25=new ListNode(10); node11.next=node12; node12.next=node13; node13.next=node14; node14.next=node15; node21.next=node22; node22.next=node23; node23.next=node24; node24.next=node25; ListNode node=test.Merge(node11,node22); while(node!=null) { System.out.print(node.val+"->"); node=node.next; } }}

輸出結果： 1->2->3->4->5->6->7->8->9->10