题目25：合并两个排序的链表
输入两个递增排序的链表，合并这两个链表并使新链表中的结点仍然是按照递增排序的
举例说明
链表1：10 -> 30 -> 50 -> 70；链表2：20 -> 40 -> 60 -> 80
合并后的链表为：10 -> 20 -> 30 -> 40 -> 50 -> 60 -> 70 -> 80
思路
几个点
- 选择好 合并后链表的头
- 每次相当于从一个老链表断开(用.next后移)，接在新链表上（为.next赋值）
一. 递归
每次以两个链表头节点中的小值作为合并链表的下一个节点。每次合并的操作都是相同的，故使用递归。
主体代码
public static ListNode merge1(ListNode head1, ListNode head2) {//递归
if (head1 == null) {
return head2;
}
if (head2 == null) {
return head1;
}
ListNode tmp = head1;//两个链表中头部较小的结点 是 新链表的头
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();//逻辑头结点
ListNode cur = root;// 待处理节点，每次都是正在合并后链表的尾，迭代向后
while (head1 != null && head2 != null) {// 当两个链表都不为空就进行合并操作
if (head1.value < head2.value) {
cur.next = head1;//老链表节点 加入新链表（接上链子）
head1 = head1.next;//老链表中 待处理节点后移（在老链表移除处理过的 节点）
} else {
cur.next = head2;
head2 = head2.next;
}
cur = cur.next;//新链表中 待处理指针后移，方便下次添加
}
// 下面的两个if有且只一个if会内的内容会执行
if (head1 != null) {// 如果第一个链表的元素未处理完将其
cur.next = head1;//接到合并链表的最后一个结点之后
}
if (head2 != null) {
cur.next = head2;
}
return root.next;//root是逻辑头结点 ；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;//两个链表中头部较小的结点 是 新链表的头
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();//逻辑头结点
ListNode cur = root;// 待处理节点，每次都是正在合并后链表的尾，迭代向后
while (head1 != null && head2 != null) {// 当两个链表都不为空就进行合并操作
if (head1.value < head2.value) {
cur.next = head1;//老链表节点 加入新链表（接上链子）
head1 = head1.next;//老链表中 待处理节点后移（在老链表移除处理过的 节点）
} else {
cur.next = head2;
head2 = head2.next;
}
cur = cur.next;//新链表中 待处理指针后移，方便下次添加
}
// 下面的两个if有且只一个if会内的内容会执行
if (head1 != null) {// 如果第一个链表的元素未处理完将其
cur.next = head1;//接到合并链表的最后一个结点之后
}
if (head2 != null) {
cur.next = head2;
}
return root.next;//root是逻辑头结点 ；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
