题解思路

双指针遍历：两个指针或是同方向访问两个链表、或是同方向访问一个链表（快慢指针）、或是相反方向扫描（对撞指针）

这里采用同方向访问两个链表的双指针。

首先考虑其中一个链表为空的情况，直接返回另一个链表头；

新建一个链表头，比较两个链表头的大小，选择小的那个节点接在新的链表头后面，然后把该链表上的指针向后移一位（只移动被添加的链表上的指针）；

如果两个链表有剩余，直接接在后面；

最后，返回新链表头的下一个节点即可。

空间复杂度：O(1)，没有新建空间，用的都是已有链表的节点所占空间。

-----

吸收

• 不同类型的双指针
• 可以新建一个链表头，方便接收两个链表中的来的节点；
• 分析空间复杂度时，并不是新建一个链表就是 O(n) 的复杂度，如果新链表只把原来链表中的节点拼接起来，那么空间复杂度是 O(1)

-----

原来的思路

在两个链表间来回循环，做 in-place 操作：

但代码写起来很复杂，需要不断在两个链表间查找插入点；并且有很多难以考虑的情况，如：

【1，2，3】和 【3，3，3】；【1，3，5】和 【1，3，5】

遂放弃