数据结构与算法之【合并有序链表】详解

题目描述

有如下有序链表 n1, n2:

1 -> 5 -> 9

1 -> 3 -> 6 -> 10

要求对链表进行合并,合并后的新链表依然有序:

1 -> 1 -> 3 -> 5 -> 6 -> 9 -> 10

题目解析

由于链表是有序的,因此在遍历 n1, n2 的过程中,只需比较出两个链表较小的节点,将该节点追加在新链表末尾即可。比较步骤分解如下:

  1. 创建一个空节点,表示新链表头部,创建两个引用,记为 head, tmp,均指向头节点。head 用于返回新链表,tmp 用于追加链表节点。

数据结构与算法之【合并有序链表】详解

  1. 比较 n1, n2, n1 <= n2 (注意相等的情况),将 n1 追加在 head 末尾,n1 指向的当前节点不再参与后续比较,移动 n1, tmp。

数据结构与算法之【合并有序链表】详解

  1. n2 < n1,追加 n2,移动 n2, tmp。

数据结构与算法之【合并有序链表】详解

  1. n2 < n1,追加 n2,移动 n2, tmp。

数据结构与算法之【合并有序链表】详解

  1. n1 <= n2,追加 n1,移动 n1, tmp。

数据结构与算法之【合并有序链表】详解

  1. n2 < n1,追加 n2,移动 n2, tmp。

数据结构与算法之【合并有序链表】详解

  1. n1 <= n2,追加 n1,移动 n1, tmp。

数据结构与算法之【合并有序链表】详解

  1. 此时 n1 指向了空,将 n2 直接追加在 tmp 后面即可。至此合并结束,tmp 无需再移动,head.next 就是新链表的头节点。

数据结构与算法之【合并有序链表】详解

经过上述分析,可以得出解题步骤:

  • 遍历 n1, n2 链表,将值较小的节点追加在 tmp 节点后,移动 tmp 和较小值节点引用;
  • 当 n1, n2 任意一方遍历到空时,停止遍历,将非空的一方追加在 tmp 后;
  • 返回 head 的下一个节点。

代码实现

代码实现如下:

/**
 * 合并两个有序链表,合并后的链表依然有序
 *
 * @param n1
 * @param n2
 * @return
 */
public static Node mergeSortedLinkedList(Node n1, Node n2) {

	if (n1 == null && n2 == null) {
		throw new RuntimeException("n1, n2 不能都为空");
	}

	if (n1 == null) {
		return n2;
	}

	if (n2 == null) {
		return n1;
	}

	//创建空的头节点
	Node head = new Node();

	//创建临时引用,用于追加节点
	Node tmp = head;

	do {
		if (n1.num <= n2.num) {
			//若 n1 小,则追加 n1,同时 n1 后移
			tmp.next = n1;
			n1 = n1.next;
		} else {
			//若 n2 小,则追加 n2,同时 n2 后移
			tmp.next = n2;
			n2 = n2.next;
		}

		//追加节点后,tmp 后移
		tmp = tmp.next;

		//当 n1, n2 均不为空时,继续比较
	} while (n1 != null && n2 != null);

	if (n1 == null) {
		//若 n1 为空,则追加 n2 整体
		tmp.next = n2;
	} else {
		//若 n2 为空,则追加 n1 整体
		tmp.next = n1;
	}

	//置空 tmp,便于垃圾回收
	tmp = null;

	//返回新链表的起始引用
	return head.next;
}

结果验证

有如下测试代码:

// 创建链表:1 -> 5 -> 9
Node n1 = new Node(1);
n1.next = new Node(5);
n1.next.next = new Node(9);

//创建链表:1 -> 3 -> 6 -> 10
Node n2 = new Node(1);
n2.next = new Node(3);
n2.next.next = new Node(6);
n2.next.next.next = new Node(10);

//合并有序链表 n1, n2
Node head = mergeSortedLinkedList(n1, n2);

System.out.println("n1: " + show(n1));
System.out.println("n2: " + show(n2));
System.out.println("合并后的链表:" + show(head));

输出如下:

n1: [Node{num=1}, Node{num=5}, Node{num=9}]
n2: [Node{num=1}, Node{num=3}, Node{num=6}, Node{num=10}]
合并后的链表: [Node{num=1}, Node{num=1}, Node{num=3}, Node{num=5}, Node{num=6}, Node{num=9}, Node{num=10}]

结果如预期。

上一篇:PAT乙级 1071 小赌怡情(C实现)


下一篇:c艹进阶编程(1)