Merge two sorted linked lists and return it as a new sorted list. The new list should be made by splicing together the nodes of the first two lists.

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

题意：将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

---

思路1：双指针。通过多次使用三元表达式，简化代码。代码如下：

class Solution {
public:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {ListNode newHead(0), *rear = &newHead;while (l1 && l2) { //都不为空指针bool judge = l1->val <= l2->val; //多次用三元表达式rear->next = judge ? l1 : l2;judge ? (l1 = l1->next) : (l2 = l2->next); rear = rear->next; }rear->next = l1 ? l1 : l2;return newHead.next;}
};

效率如下

执行用时：12 ms, 在所有 C++ 提交中击败了49.80% 的用户
内存消耗：14.1 MB, 在所有 C++ 提交中击败了39.71% 的用户

---

思路2：双指针+交换。通过交换指针，始终合并 l1 指向的结点，最后合并剩下的链表。代码如下：

class Solution {
public:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {ListNode newHead(0), *rear = &newHead;while (l1 && l2) {if (l1->val > l2->val) swap(l1, l2);rear->next = l1;l1 = l1->next;rear = rear->next;}rear->next = l1 ? l1 : l2;return newHead.next;}
}; 

提交后效率如下：

执行用时：4 ms, 在所有 C++ 提交中击败了98.11% 的用户
内存消耗：14.1 MB, 在所有 C++ 提交中击败了21.45% 的用户

---

思路3：递归实现。递归基准是：都为空、或者一个链表指针为空。递归体是：

• 如果 l1->val 更小，就递归合并 l1->next, l2 ，将返回的指针接到 l1->next ；
• 如果 l2->val 更小，就递归合并 l1, l2->next ，将返回的指针接到 l2->next ；

代码如下：

class Solution {
public:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {if (l1 == nullptr) return l2;if (l2 == nullptr) return l1;if (l1->val <= l2->val) {l1->next = mergeTwoLists(l1->next, l2);return l1;} else {l2->next = mergeTwoLists(l1, l2->next);return l2;}}
};

效率如下：

执行用时：4 ms, 在所有 C++ 提交中击败了98.11% 的用户
内存消耗：13.9 MB, 在所有 C++ 提交中击败了98.87% 的用户

简化一下上述代码。这里使用 res 指向 l1, l2 两者中值较小的，然后递归合并 res->next 和 l1, l2 中值较大的指针：

class Solution {
public:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {if (l1 == nullptr) return l2;if (l2 == nullptr) return l1;ListNode *res = l1->val <= l2->val ? l1 : l2;res->next = mergeTwoLists(res->next, l1->val > l2->val ? l1 : l2);return res;}
};