LeetCode 21：合并两个有序链表 Merge Two Sorted Lists

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

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

示例：

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

解题思路：

迭代和递归都能解题。无非是依次将两个链表每个节点的值对比，取出值较小的节点，添加到新链表末尾。然后继续比较两个链表，直到其中一个链表遍历完成，此时另一个链表剩余所有节点直接添加到新链表之后即可。其逻辑为：

原链表：1->2->4->null，1->3->4->5->6->null
依次对比节点值，取出各自头节点：1 = 1
值相同取出一个节点 1，组成新链表：1
此时原链表：2->4->null，1->3->4->5->6->null

对比头节点值：2 > 1
取出 1 节点，添加到新链表末尾：1->1
此时原链表：2->4->null，3->4->5->6->null

对比头节点值：2 < 3
取出 2 节点，添加到新链表末尾：1->1->2
此时原链表：4->null，3->4->5->6->null

.......依次类推，直到其中一个原链表为空时：

原链表：null，4->5->6->null
新链表：1->1->2->3->4
这时其中一个原链表已经为空，则直接将另一个原链表添加到新链表末尾即可：
1->1->2->3->4->4->5->6->null

迭代法：

迭代法需要注意：先判断原链表是否为空；对比原链表第一个节点值的大小，选择较小一个作为新链表的头节点。之后才能按上述逻辑执行。

如果添加一个虚拟节点作为头节点，则无需上述条件，但应当返回虚拟节点的下一个节点。

Java：

class Solution {    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {        ListNode head = new ListNode(-1);//新建虚拟头节点        ListNode cur = head;//当前节点指向虚拟头节点        while (l1 != null && l2 != null) {//循环条件为链表都不为空            if (l1.val < l2.val) {//比较头节点的值的大小                cur.next = l1;//当前节点连接到节点值较小的一个                l1 = l1.next;//刷新原链表头节点                cur = cur.next;//刷新当前节点            } else {                cur.next = l2;                l2 = l2.next;                cur = cur.next;            }        }        if (l1 == null) cur.next = l2;//选择另外一个不为空的原链表，连接到新链表末尾        else cur.next = l1;        return head.next;//返回虚拟头节点的下一个节点，即真实头节点    }}

Python3：

class Solution:    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:        head = ListNode(-1)        cur = head;        while l1 and l2:            if l1.val <= l2.val:                cur.next = l1                cur = cur.next                l1 = l1.next            else:                cur.next = l2                cur = cur.next                l2 = l2.next        if l1:            cur.next = l1        else:            cur.next = l2        return head.next

递归法：

递归基线条件为：原链表其中之一遇到空节点。返回值为：另一个链表剩余部分的头节点。

递归判断头节点的值的大小，取小的节点添加到新链表之后。将剩余链表传回递归函数。

Java：

class Solution {    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {        if (l1 == null) return l2;//基线条件        if (l2 == null) return l1;//基线条件        ListNode head;        if (l1.val <= l2.val) {//选择节点值较小的节点            head = l1;//刷新头节点            head.next = mergeTwoLists(l1.next, l2);//剩余链表作为参数传入递归函数        } else {            head = l2;            head.next = mergeTwoLists(l1, l2.next);        }        return head;    }}

Python3：

class Solution:    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:        if not l1: return l2        if not l2: return l1        if l1.val <= l2.val:            head = l1            head.next = self.mergeTwoLists(l1.next, l2)        else:            head = l2            head.next = self.mergeTwoLists(l1, l2.next)        return head

欢迎关注公.众号：爱写Bug