25:合并两个排序的链表

发表于 | 分类于

题目25：合并两个排序的链表

输入两个递增排序的链表，合并这两个链表并使新链表中的结点仍然是按照递增排序的。

举例说明

链表1：10 -> 30 -> 50 -> 70；链表2：20 -> 40 -> 60 -> 80
合并后的链表为：10 -> 20 -> 30 -> 40 -> 50 -> 60 -> 70 -> 80

思路

几个点

  • 选择好 合并后链表的头
  • 每次相当于从一个老链表断开(用.next后移)，接在新链表上（为.next赋值）

一. 递归

每次以两个链表头节点中的小值作为合并链表的下一个节点。每次合并的操作都是相同的，故使用递归。

主体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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;
}

二. 迭代

主体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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是合并后的链表头
}

总的代码含测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
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
2
3
原始链表1：10->30->50->70->null
原始链表2：20->40->60->80->null
合并后的链表：10->20->30->40->50->60->70->80->null
> >