可视化图解算法06：合并两个有序（排序）的链表
1. 题目描述
输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。
数据范围：10000≤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
输入：
{1,3,5},{2,4,6}返回值：
{1,2,3,4,5,6}示例2
输入：
{},{}返回值：
{}示例3
输入：
{-1,2,4},{1,3,4}返回值：
{-1,1,2,3,4,4}2. 解题思路
假如要合并的两个链表分别为： 1→3→5与 2→4→6，对他们两个链表合并，合并之后的链表为： 1→2→3→4→5→6。结构如下图所示。
第一步：定义临时虚拟头节点与指针变量。指针变量有3个，cur用于操作的链表，h1用于链表1节点值的对比，h2用于链表2节点值的对比。
第二步：循环合并两个链表。
首先比较h1与h2指向节点的值，这时1 谢谢分享，试用一下 谢谢分享，辛苦了 东西不错很实用谢谢分享 分享、互助 让互联网精神温暖你我 谢谢楼主提供！ 很好很强大我过来先占个楼 待编辑 懂技术并乐意极积无私分享的人越来越少。珍惜 谢谢分享，试用一下 这个有用。 很好很强大我过来先占个楼 待编辑 收藏一下 不知道什么时候能用到 分享、互助 让互联网精神温暖你我 这个好，看起来很实用 这个好，看起来很实用 过来提前占个楼 感谢分享，学习下。 懂技术并乐意极积无私分享的人越来越少。珍惜 收藏一下 不知道什么时候能用到 鼓励转贴优秀软件安全工具和文档！
页:
[1]
2