題目25：合并兩個排序的鏈表
輸入兩個遞增排序的鏈表，合并這兩個鏈表并使新鏈表中的結(jié)點(diǎn)仍然是按照遞增排序的
舉例說明
鏈表1：10 -> 30 -> 50 -> 70债蓝；鏈表2：20 -> 40 -> 60 -> 80
合并后的鏈表為：10 -> 20 -> 30 -> 40 -> 50 -> 60 -> 70 -> 80
思路
幾個點(diǎn)
- 選擇好 合并后鏈表的頭
- 每次相當(dāng)于從一個老鏈表斷開(用.next后移)壳鹤，接在新鏈表上（為.next賦值）
一. 遞歸
每次以兩個鏈表頭節(jié)點(diǎn)中的小值作為合并鏈表的下一個節(jié)點(diǎn)。每次合并的操作都是相同的饰迹，故使用遞歸芳誓。
主體代碼
public static ListNode merge1(ListNode head1, ListNode head2) {//遞歸
if (head1 == null) {
return head2;
}
if (head2 == null) {
return head1;
}
ListNode tmp = head1;//兩個鏈表中頭部較小的結(jié)點(diǎn) 是 新鏈表的頭
if (tmp.value < head2.value) {
tmp.next = merge1(head1.next, head2);
} else {
tmp = head2;
tmp.next = merge1(head1, head2.next);
}
return tmp;
}
二. 迭代
主體代碼
public static ListNode merge2(ListNode head1, ListNode head2) {//迭代
if (head1 == null) {
return head2;
}
if (head2 == null) {
return head1;
}
ListNode root = new ListNode();//邏輯頭結(jié)點(diǎn)
ListNode cur = root;// 待處理節(jié)點(diǎn)讯嫂，每次都是正在合并后鏈表的尾，迭代向后
while (head1 != null && head2 != null) {// 當(dāng)兩個鏈表都不為空就進(jìn)行合并操作
if (head1.value < head2.value) {
cur.next = head1;//老鏈表節(jié)點(diǎn) 加入新鏈表（接上鏈子）
head1 = head1.next;//老鏈表中 待處理節(jié)點(diǎn)后移（在老鏈表移除處理過的 節(jié)點(diǎn)）
} else {
cur.next = head2;
head2 = head2.next;
}
cur = cur.next;//新鏈表中 待處理指針后移兆沙，方便下次添加
}
// 下面的兩個if有且只一個if會內(nèi)的內(nèi)容會執(zhí)行
if (head1 != null) {// 如果第一個鏈表的元素未處理完將其
cur.next = head1;//接到合并鏈表的最后一個結(jié)點(diǎn)之后
}
if (head2 != null) {
cur.next = head2;
}
return root.next;//root是邏輯頭結(jié)點(diǎn) 欧芽；root.next是合并后的鏈表頭
}
總的代碼含測試
public class _25 {
private static class ListNode {
int value;
ListNode next;
public ListNode() {
}
public ListNode(int value) {
this.value = value;
}
}
public static ListNode merge1(ListNode head1, ListNode head2) {//遞歸
if (head1 == null) {
return head2;
}
if (head2 == null) {
return head1;
}
ListNode tmp = head1;//兩個鏈表中頭部較小的結(jié)點(diǎn) 是 新鏈表的頭
if (tmp.value < head2.value) {
tmp.next = merge1(head1.next, head2);
} else {
tmp = head2;
tmp.next = merge1(head1, head2.next);
}
return tmp;
}
public static ListNode merge2(ListNode head1, ListNode head2) {//迭代
if (head1 == null) {
return head2;
}
if (head2 == null) {
return head1;
}
ListNode root = new ListNode();//邏輯頭結(jié)點(diǎn)
ListNode cur = root;// 待處理節(jié)點(diǎn)，每次都是正在合并后鏈表的尾葛圃，迭代向后
while (head1 != null && head2 != null) {// 當(dāng)兩個鏈表都不為空就進(jìn)行合并操作
if (head1.value < head2.value) {
cur.next = head1;//老鏈表節(jié)點(diǎn) 加入新鏈表（接上鏈子）
head1 = head1.next;//老鏈表中 待處理節(jié)點(diǎn)后移（在老鏈表移除處理過的 節(jié)點(diǎn)）
} else {
cur.next = head2;
head2 = head2.next;
}
cur = cur.next;//新鏈表中 待處理指針后移千扔，方便下次添加
}
// 下面的兩個if有且只一個if會內(nèi)的內(nèi)容會執(zhí)行
if (head1 != null) {// 如果第一個鏈表的元素未處理完將其
cur.next = head1;//接到合并鏈表的最后一個結(jié)點(diǎn)之后
}
if (head2 != null) {
cur.next = head2;
}
return root.next;//root是邏輯頭結(jié)點(diǎn) ；root.next是合并后的鏈表頭
}
//for test
public static void printList(ListNode head) {
while (head != null) {
System.out.print(head.value + " -> ");
head = head.next;
}
System.out.println("null");
}
public static void main(String[] args) {
// 10 -> 30 -> 50 -> 70
ListNode head1 = new ListNode(10);
ListNode n2 = new ListNode(30);
ListNode n3 = new ListNode(50);
ListNode n4 = new ListNode(70);
head1.next = n2;
n2.next = n3;
n3.next = n4;
// 20 -> 40 -> 60 -> 80
ListNode head2 = new ListNode(20);
ListNode n5 = new ListNode(40);
ListNode n6 = new ListNode(60);
ListNode n7 = new ListNode(80);
head2.next = n5;
n5.next = n6;
n6.next = n7;
System.out.print("原始鏈表1：");
printList(head1);
System.out.print("原始鏈表2：");
printList(head2);
System.out.print("合并后的鏈表：");
//head = merge1(head, head2);
head1 = merge2(head1, head2);
printList(head1);
}
}
輸出：
原始鏈表1：10->30->50->70->null
原始鏈表2：20->40->60->80->null
合并后的鏈表：10->20->30->40->50->60->70->80->null
