如何高效合并两个已排序的链表？

本文共计917个文字，预计阅读时间需要4分钟。

合并两个有序链表，并输出合并后的链表。

输入：两个单调递增的链表

输出：合并后的链表，当且仅当需要合并后的链表满时输出

示例：输入：

1-> 2 -> 4

1-> 3 -> 4

输出：

1-> 1 -> 2 -> 3 -> 4

合并两个有序链表

“Think ahead. Don't let day-to-day operations drive out planning.” — Donald Rumsfeld

题目描述

---

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足递增有序的规则。

示例1：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

限制：

0 <= 链表长度 <= 1000

解题思路一：递归法

由于链表是升序排列，如果链表 1 的头结点小于链表 2 的头结点的值，那么链表 1 的头结点就是合并后链表的头结点。

并将下一层递归函数的返回值，链接到当前结点的尾部。