有序链表的合并

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

示例：

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

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

---

分析法

双指针法，维持两个指针l1,l2分别遍历两个链表，分两种情况处理：

总结  谁小合并谁

---

---

l1->val < l2->val ，那么合并的下一个节点是l1，同时l1前进一个节点

l1->val >= l2->val , 那么合并的下一个节点时l2，同时l2前进一个节点

直到l1和l2有一个到达链表尾结束遍历，如果两个链表不等长，那此时肯定有一个链表没走完，将这个链表剩下没走完的那部分加到合并的新链表尾部即可

时间复杂度：O(m+n)

空间复杂度：O(1)

---

递归解析

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:

            res = l1

            res.next = self.mergeTwoLists(l1.next,l2)

        else:

            res = l2

            res.next = self.mergeTwoLists(l1,l2.next)

        return res

---

一般解析

    def mergeTwoLists(self, l1, l2):

        """

        :type l1: ListNode

        :type l2: ListNode

        :rtype: ListNode

        """

        if not l1 and not l2:  # l1和l2链表均不存在

            return None

        if not l1:  # l1链表不存在

            return l2

        if not l2:  # l2链表不存在

            return l1

        l3 = ListNode(0)

        l3_head_node = l3

        while l1 is not None and l2:

            if l1.val <= l2.val:

                l3.next = l1

                l1 = l1.next

            else:

                l3.next = l2

                l2 = l2.next

            l3 = l3.next

        if l1 is not None:

            l3.next = l1

        else:

            l3.next = l2

        return l3_head_node.next