面试 14：算法之合并两个排序链表
终于又回到了我们的算法习题讲解了。南尘发现最近文章阅读量明显比以前少了不少，就上门请教小伙伴原因。他们都说作为一名 Android 应用开发工程师，实在是在工作中没有接触到算法。做技术这个东西，学习了还是得练，不练过几天一定会忘掉。
不过想必大家读南尘的文章也是深有所感，基本都是站在一个极其普通的程序员角度思考的，层次感也不会突如其来。所以，大家还望多多思考呀，算法这个东西是练出来的，不是看出来的。
不过呢，不喜欢算法系列推文的小伙伴也大可不必担心，在算法之后的板块就是 Java 基础啦。
有句话说的好，面试造航母，入职拧螺丝。实际上也是这样，面试官极难通过简单的面试了解到你这个人的能力，而手写算法却是最适合看出一个人写代码的习惯和程序思维的，这也是大公司以及不少小公司慢慢转向算法面试的一个原因吧~
好了，话不多说，我们直接来看今天的面试题。
面试题：输入两个递增排序的单链表，data 域为 int 型值。合并这两个链表，并使新链表中的结点也是按照递增排序的。例如链表 A：1->3->5，链表 B：2->4，那它们合并后就是 1->2->3->4->5
看到这样的题，我们一定要学会先在心中想好测试用例，再思考程序逻辑。写完程序逻辑后，再把自己事先想好的测试用例测试通过后再交给面试官。事实上，面试官也是事先准备了测试用例的。
而对于测试用例，就一定要注意好之前南尘给大家讲的边界值。只有能通过边界值、错误值的程序，才拥有足够的健壮性。
我们回到题干，输入的是两个递增排序的单链表，我们需要合并它，得到的新链表也是递增排序的。在心中不难拥有这样的思路。
假设单链表 A：1->3，单链表 B：2->4->5；
先比较 A、B 链表的头结点，这里 1 < 2，所以把 1 作为新链表的头结点；
1 从 A 链表脱离，3 成为了 A 链表的头结点；
再进行第二步的比较，3 > 2，把 B 链表的头结点值 2 接到新链表上，得到 1->2；
一直执行类似 2~4 的步骤，直到 A 链表脱离完，新链表是 1->2->3 ，B 链表是 4->5，A 链表已经为 null；
此时直接把 B 链表全部接到新链表上，得到最后结构 1->2->3->4->5；
我们不得不想到边界值和错误值，假设输入的 A 链表为 null，则新链表直接为 B。B 链表为 null，新链表为 A。 A、B 都为 null，则新链表也为 null。
我们既然是重复的步骤，那我们一定首先能想到递归的思路。我们极容易得到下面的代码。
public class Test14 {
public static class Node {
int data;
Node next;
Node(int data) {
this.data = data;
}
}
private static Node merge(Node head1, Node head2) {
// 如果链表 1 为 null ,新链表直接为 2 链表；
if (head1 == null)
return head2;
// 如果链表 2 为 null,则新链表直接为 1 链表
if (head2 == null)
return head1;
Node head = null;
// 假设链表 1 的头结点值小于等于链表 2；则直接把链表 1 的头结点赋值为新链表，并递归新的 1 链表
if (head1.data <= head2.data) {
head = head1;
head.next = merge(head1.next, head2);
} else {
// 否则，对链表 2 执行同样的操作，并把脱离的值赋值上去
head = head2;
head.next = merge(head1, head2.next);
}
return head;
}
public static void main(String[] args) {
Node head1 = new Node(1);
head1.next = new Node(3);
head1.next.next = new Node(5);
head1.next.next.next = new Node((7));
Node head2 = new Node(2);
head2.next = new Node(4);
head2.next.next = new Node(6);
head2.next.next.next = new Node(8);
Node head = merge(head1, head2);
while (head != null) {
System.out.print(head.data + "->");
head = head.next;
}
System.out.print("null");
}
}
写出了代码后，自然不能忘了用事先想好的测试用例去测试一遍流程，这里测试是没有问题的。
事实上，这也是《剑指 Offer》的标准解法。递归解法有个好处，就是比较容易想到，但这应该是建立在建模能力比较强的基础之上。但往往不少人会觉得递归特别绕，容易把人绕晕，而且在空间利用率上一直都表现不好，有的面试官就是不能接受递归的代码，所以本题我们更加推荐的是迭代的方式处理。
迭代处理
回到我们前面的思路中，上面我们用的方式是不断「脱落」，然后把暴露出来的结点当做一个新的头结点来处理，相信不少小伙伴不怎么能接受这个思路。那我们换个更好理解的方式，我们就直接用我们链表常用的指针移动的方式来处理，我们看行不行。
所以我们开始直接编写。
private static Node merge(Node head1, Node head2) {
if (head1 == null)
return head2;
if (head2 == null)
return head1;
// 上面的不用说，就是处理传入值为 null 的情况
Node head = null;
// 当两个链表都不为空就可以比较大小来确定接哪个
while (head1 != null && head2 != null) {
if (head1.data <= head2.data) {
head = head1;
head1 = head1.next;
} else {
head = head2;
head2 = head2.next;
}
}
// 如果第一个链表的元素未处理完毕，则把剩余的链表接到最后一个链表后
if (head1 != null)
head.next = head1;
// 同理，如果第二个链表的元素未处理完毕，就把剩余的链表接到新链表的尾结点
if (head2 != null)
head.next = head2;
return head;
}
同样写完后，拿出我们的测试用例开始测试，首先肯定是功能测试。
假定我们的链表 A 为：1->3，链表 B 为: 2->4->5;
都不为空进入 while 循环，因为 1 < 2，执行 head = head1，所以新链表为：1->3->null；head1 = head1.next，指针后移；
依然满足 whild 循环条件，因为 3 > 2，所以新链表为，head = head2 ；等等，这里出了问题，我根本没接到前面放的 head1 的后面，所以这样的赋值明显是不对的。
功能测试就出了问题，我们当然得思考如何修改，正常来说，我们希望新链表的 1.next = 2，所以我们肯定不能直接用 head = head2 这样的表达式来进行赋值。
我们一定的有个类似 head.next = head2，然后用类似 head = head.next 这样的方式向后遍历才是正确的。所以我们修改一下代码：
private static Node merge(Node head1, Node head2) {
if (head1 == null)
return head2;
if (head2 == null)
return head1;
// 上面的不用说，就是处理传入值为 null 的情况
// 为了下面的 head.next，所以我们首先肯定得初始化一个 Node
Node head = new Node();
// 当两个链表都不为空就可以比较大小来确定接哪个
while (head1 != null && head2 != null) {
if (head1.data <= head2.data) {
head.next = head1;
head1 = head1.next;
} else {
head.next = head2;
head2 = head2.next;
}
head = head.next;
}
// 如果第一个链表的元素未处理完毕，则把剩余的链表接到最后一个链表后
if (head1 != null)
head.next = head1;
// 同理，如果第二个链表的元素未处理完毕，就把剩余的链表接到新链表的尾结点
if (head2 != null)
head.next = head2;
return head;
}
再次进行功能测试：
假定 A：1->3，B：2->4->5，先初始化 head，最开始肯定两个都不为空的，所以直接比较；
因为 1 < 2 , 所以新链表为 0->1->3->null，链表 A 指针后移；head = head.next，所以新的 head 值为 1；
继续循环，因为 3 > 2，所以得到新的 head.next = head2， 即有 1->2；
以此类推，最终得到 head 一直得到的历史为 1，2，3。此时链表 A 已经遍历完，链表 B 的指针指向 4；
退出 while 循环，满足 head2 != null，接到 head 后面， head.next = head2，此时的 head2 里面还剩下 4->5->null；
返回 head。等等，这里还是有问题，我们一直在让新链表的指针后移，这样返回出来的就是尾结点了。但我们想要的答案必须是头结点才可以遍历；
所以我们必须在 while 循环前面放头结点的值。需要注意的是，由于我们要用到 head.next，所以我们最后真正的头结点实际上是 head.next。
完整代码如下：
public class Test14 {
public static class Node {
int data;
Node next;
Node(int data) {
this.data = data;
}
Node() {
}
}
private static Node merge(Node head1, Node head2) {
if (head1 == null)
return head2;
if (head2 == null)
return head1;
// 上面的不用说，就是处理传入值为 null 的情况
// 为了下面的 head.next，所以我们首先肯定得初始化一个 Node
Node head = new Node();
Node temp = head;
// 当两个链表都不为空就可以比较大小来确定接哪个
while (head1 != null && head2 != null) {
if (head1.data <= head2.data) {
head.next = head1;
head1 = head1.next;
} else {
head.next = head2;
head2 = head2.next;
}
head = head.next;
}
// 如果第一个链表的元素未处理完毕，则把剩余的链表接到最后一个链表后
if (head1 != null)
head.next = head1;
// 同理，如果第二个链表的元素未处理完毕，就把剩余的链表接到新链表的尾结点
if (head2 != null)
head.next = head2;
return temp.next;
}
public static void main(String[] args) {
Node head1 = new Node(1);
head1.next = new Node(3);
head1.next.next = new Node(5);
head1.next.next.next = new Node((7));
Node head2 = new Node(2);
head2.next = new Node(4);
head2.next.next = new Node(6);
head2.next.next.next = new Node(8);
Node head = merge(head1, head2);
while (head != null) {
System.out.print(head.data + "->");
head = head.next;
}
System.out.print("null");
}
}
写完后，还是得过一遍测试用例。
当传入的 head1 或者 head2 为 null 的时候，直接返回另外一条链表，都为 null ，就返回 null;
当传入 A：1->3，B：2->4->5，上面已经例证，符合条件；
当传入相等值：A：1->3->5，B：1->2->4，符合条件；
当传入两个链表均只有一个结点的，A：1，B：2，符合条件。
基本还是没毛病，这时候我们就可以交上自己的答卷啦~
基本步骤很清晰：思考测试用例 => 思考程序逻辑 => 拿测试用例进去验证 => 发现问题直接更改 => 测试用例验证，注意边界值 => 测试通过。
如果保持上面这样的步骤，实在想不明白，在纸上画画思路，相信即使你没有做到 100% 正确，你给面试官的感觉也是足够靠谱的。
好啦，今天的面试题就先到这里，不知道大家有没有被南尘绕晕呀，绕晕了没事儿，多体验几次就好了。
还是要提醒大家：千万要自己去练习，看懂不思考，这样的学习效率是极低的！
好啦，明天的习题我们先放一下，别忘了先思考思考，并动手练练~
题目：输入一个矩阵，按照从外向里以顺时针的顺序依次打印每一个数字。例如输入：
{{1，2，3},
{4，5，6},
{7，8，9}}
则依次打印数字为 1、2、3、6、9、8、7、4、5
—————END—————
我是南尘，只做比心的公众号，欢迎关注我。
推荐阅读：
欢迎关注南尘的公众号：nanchen
做不完的开源，写不完的矫情，只做比心的公众号，如果你喜欢，你可以选择分享给大家。如果你有好的文章，欢迎投稿，让我们一起来分享。