可视化图解算法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. {1,3,5},{2,4,6}

复制代码

返回值：

1. {1,2,3,4,5,6}

复制代码

示例2

输入：

1. {},{}

复制代码

返回值：

1. {}

复制代码

示例3

输入：

1. {-1,2,4},{1,3,4}

复制代码

返回值：

1. {-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