合并兩個有序鏈表是很常見的一個鏈表相關的演算法題，因為當時在練習這個題的時候，剛學完排序演算法沒多久，所以我在練這個題的時候第一反應就是使用歸并排序的“并”的思想，當然，我并沒有去算過這個演算法的時間復雜度，因為目前階段只要能做出來就好了，哈哈哈（來自一個演算法菜鳥的興奮！！！），代碼如下（雖然代碼看起來有點啰嗦，其實還是很簡單的，很多代碼都一樣）：
1 /**
2 * 合并兩個有序串列，思路參考歸并排序的并程序
3 */
4 public class MergeTwoLinked {
5 public static void main(String[] args) {
6 ListNode node1=new ListNode(1);
7 ListNode node2=new ListNode(2);
8 ListNode node3=new ListNode(3);
9 ListNode node4=new ListNode(4);
10 node3.next=node4;
11 node2.next=node3;
12 node1.next=node2;
13
14 ListNode node5=new ListNode(0);
15 ListNode node6=new ListNode(1);
16 ListNode node7=new ListNode(2);
17 ListNode node8=new ListNode(4);
18 node7.next=node8;
19 node6.next=node7;
20 node5.next=node6;
21
22 ListNode head = mergeTwoLinked(node1, node5);//呼叫合并方法
23 while (head!=null){//輸出鏈表節點
24 System.out.println(head.toString());
25 head=head.next;
26 }
27 }
28
29 /**
30 * 合并兩個有序串列，思路參考歸并排序的并程序
31 * @param head1
32 * @param head2
33 * @return 回傳合并后的鏈表
34 */
35 public static ListNode mergeTwoLinked(ListNode head1, ListNode head2) {
36 if(head1==null && head2==null){//當兩個鏈表都為空時回傳null
37 return null;
38 }else if(head1!=null && head2==null){//當第2個鏈表為null時回傳第1個鏈表
39 return head1;
40 }else if(head1==null && head2!=null){//當第1個鏈表為null時回傳第2個鏈表
41 return head2;
42 }
43 ListNode head;//定義合并后的鏈表的頭指標
44 ListNode next;//用于記錄新鏈表的頭結點的下一個節點
45 //當第1個鏈表的第一個節點的值小于第2個鏈表的第一個節點的值時，將新鏈表的頭結點指向第1個鏈表
46 if(head1.val<head2.val){
47 next=head1.next;
48 head1.next=null;
49 head=head1;
50 head1=next;
51 }else{//當第1個鏈表的第一個節點的值大于等于第2個鏈表的第一個節點的值時，將新鏈表的頭結點指向第2個鏈表
52 next=head2.next;
53 head2.next=null;
54 head=head2;
55 head2=next;
56 }
57 ListNode temp=head;//用于遍歷新鏈表
58 while (head1 != null && head2 != null) {//根據節點值的大小拼接到新鏈表后面，當有一個鏈表已經遍歷完后退出
59 if (head1.val<head2.val){
60 next=head1.next;
61 head1.next=null;
62 temp.next=head1;
63 head1=next;
64 temp=temp.next;
65 }else{
66 next=head2.next;
67 head2.next=null;
68 temp.next=head2;
69 head2=next;
70 temp=temp.next;
71 }
72 }
73 if (head1!=null){//當第1個鏈表不為null時，直接拼接在新鏈表后面
74 temp.next=head1;
75 }
76 if (head2!=null){//當第2個鏈表不為null時，直接拼接在新鏈表后面
77 temp.next=head2;
78 }
79 return head;
80 }
81 }
82
83 class ListNode {
84 int val;
85 ListNode next;
86
87 public ListNode(int x) {
88 val = x;
89 }
90
91 @Override
92 public String toString() {
93 return "ListNode{" +
94 "val=" + val +
95 '}';
96 }
97 }
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/276897.html
標籤：Java
上一篇：Mybatis的三種批量插入方式