21. 合并两个有序链表

题目描述：

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

示例：

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

Java解法（迭代）：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        //如果链表l1为空则返回l2，反之亦然，都为空，则返回空
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        //初始化合并后的链表的头结点，用来返回结果
        ListNode mergeList = new ListNode(-1);
        //初始化节点用来表示合并后的链表的尾节点
        ListNode mergeHead = mergeList;
        //遍历两个链表直到其中一个达到尾部
        while(l1 != null && l2 != null)
        {
            if (l1.val <= l2.val)
            {
                mergeList.next = l1;
                l1 = l1.next;
            }else{
                mergeList.next = l2;
                l2 = l2.next;
            }
            mergeList = mergeList.next;
        }
        //将l1或者l2中不为空的一个直接链接到合并链表的尾结点的后面
        mergeList.next = l1 == null ? l2 : l1;
        return mergeHead.next;
    }
}

Java解法（递归）：

1、使用递归实现，新链表也不需要构造新节点：
2、终止条件：两条链表分别名为 l1 和 l2，当 l1 为空或 l2 为空时结束
3、返回值：每一层调用都返回排序好的链表头
4、递归内容：
     1、如果 l1 的 val 值更小，将l1作为合并后链表的头结点；
     2、在剩余的节点中，l2的头节点的值如果小于l1的头节点值，那么l2的头结点就是剩余链表的头结点；
     3、把这个节点和之前已经合并后的链表的尾结点 l1.next 相接；

代码实现：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        if (l1.val < l2.val)
            {
                l1.next = mergeTwoLists(l1.next, l2);
                return l1;
            }else{
                l2.next = mergeTwoLists(l2.next, l1);
                return l2;
            }
    }
}

python3解法：

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        # write code here
        mergeHead = ListNode(0)
        curNode = mergeHead
        while pHead1 and pHead2:
            if pHead1.val < pHead2.val:
                curNode.next = pHead1
                pHead1 = pHead1.next
            else:
                curNode.next = pHead2
                pHead2 = pHead2.next
            curNode = curNode.next
        curNode.next = pHead1 if pHead1 else pHead2
        return mergeHead.next

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-two-sorted-lists