两条有序链表 合并成一条有序链表

发表于 分类于 ， ， Waline： 本文字数： 1.7k 阅读时长 ≈ 2 分钟

合并有序链表

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
/**
 * 两条有序列表合并之后仍然有序
 * 同时不断遍历两个链表，取出小的追加到新的头节点后，直至两者其中一个为空
 * 再将另一者追加的新链表最后
 * 
 * @return 两个有序的链表合并后得到的链表
 */
public static Node mergeOrderedLinkedList(Node p1, Node p2) {
	// 创建一个头节点
	Node head = new Node();
	// 尾指针指向头节点
	Node tail = head;
	// 遍历两个链表，短的链表接受后循环停止
	while (p1 != null && p2 != null) {
		// 比较两个链表中的节点
		// 如果链表1的当前节点小
		if (p1.data < p2.data) {
			// 小的链表1的当前节点连接到尾节点上。
			tail.next = p1;
			// 链表1的当前节点已经连接到结果链表上了，
			// 链表1的当前节点向前走一步
			p1 = p1.next;
		} else {
			// 如果是链表2的当前节点比较小
			// 把链表2的当前节点接到合并链表的尾节点上
			tail.next = p2;
			// 链表2的当前节点向前走一步
			p2 = p2.next;
		}
		// 合并链表尾指针向前走一步
		tail = tail.next;
	}
	// 长的链表剩下的部分接到尾节点上
	tail.next = (p1 == null) ? p2 : p1;
	return head.next;
}

测试

1
2
3
4
5
6
7
8
int[] a = { 1, 4, 5, 8, 9 };
int[] b = { 2, 3, 6, 7, 10, 11, 12 };
Node nodeA = Node.createLinkByTail(a);
Node nodeB = Node.createLinkByTail(b);
Node.printNode(nodeA);
Node.printNode(nodeB);
Node mernNode = Node.mergeOrderedLinkedList(nodeA, nodeB);
Node.printNode(mernNode);

运行结果：

1
2
3
head-->1-->4-->5-->8-->9
head-->2-->3-->6-->7-->10-->11-->12
head-->1-->2-->3-->4-->5-->6-->7-->8-->9-->10-->11-->12

颠倒上面的数组的循序：

1
2
int[] b = { 1, 4, 5, 8, 9 };
int[] a = { 2, 3, 6, 7, 10, 11, 12 };

再次运行：
运行结果：

1
2
3
head-->2-->3-->6-->7-->10-->11-->12
head-->1-->4-->5-->8-->9
head-->1-->2-->3-->4-->5-->6-->7-->8-->9-->10-->11-->12

参考资料

https://medium.com/@bittigermanager/%E7%AE%97%E6%B3%95%E5%85%A5%E9%97%A8%E5%BF%85%E8%AF%BB-merge-two-sorted-lists-%E5%90%88%E5%B9%B6%E4%B8%A4%E4%B8%AA%E6%9C%89%E5%BA%8F%E9%93%BE%E8%A1%A8-b3d64661657b

https://blog.csdn.net/biezhihua/article/details/79935765