算法题学习 --- 合并两个排序的链表
题目
描述
输入两个递增的链表，单个链表的长度为 n，合并这两个链表并使新链表中的节点仍然是递增排序的。
数据范围： 0≤n≤1000，−1000≤节点值≤1000 要求：空间复杂度 O(1)，时间复杂度 O(n)
如输入{1,3,5},{2,4,6}时，合并后的链表为{1,2,3,4,5,6}，所以对应的输出为{1,2,3,4,5,6}，转换过程如下图所示：
或输入{-1,2,4},{1,3,4}时，合并后的链表为{-1,1,2,3,4,4}，所以对应的输出为{-1,1,2,3,4,4}，转换过程如下图所示：
示例 1
示例 2
示例 3
分析
考虑特殊情况
在进行问题分析过程前，我们先考虑一下特殊情况，那么在这道问题中，有哪些情况是特殊的呢？
不难发现，如下情况：
pHead1 是空链表或者 pHead2 是空链表，那么我们只需要返回对方即可
当然两者都是空链表的情况返回对方也是可以的
考虑一般情况
由于需要按顺序排列，这里我们最先想到的就是使用两个指针分别遍历两个链表，直到两个指针中出现空指针的情况，在遍历过程中，做如下判断：
如果链表 1 的元素小于链表 2 的元素，那么先链接 1 的元素，链表 1 的指针后移；
否则，先链接 2 的元素，链表 2 的指针后移。
出现一个链表指针为空的情况，说明另一个链表的元素都比之前的元素大，这时只需要将剩余的元素链接到末尾即可。
代码示例
注意，这里还做了一些额外的处理：
pReturn:记录返回的头结点，指向较小的头结点；
pCur0:记录 merge 链表的当前位置；
pCur1:记录链表 1 的当前位置；
pCur2:记录链表 2 的当前位置。
版权声明: 本文为 InfoQ 作者【桑榆】的原创文章。
原文链接:【http://xie.infoq.cn/article/0e12b9a4c7ac0400c7f27a28f】。文章转载请联系作者。
北海虽赊，扶摇可接；东隅已逝，桑榆非晚！ 2020-02-29 加入
Android手机厂商-相机软件系统工程师 爬山/徒步/Coding
评论