[LeetCode]Merge Two Sorted Lists(Python)

1.题目要求：

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

2.题目理解：

题目需求是合并两个已排序的链表，合并后链表依然有序。

输入: 1->2->4      ，       1->3->4

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

3.解题方法：

3.1 使用迭代的方法：

此方法的基本思路是先创建一个新链表的头结点和尾节点，然后依次取两个输入链表的节点比较其值的大小，使新链表尾节点的next指向值较小的那个节点，再更新值较小的节点使其后移一个节点，最后更新新链表尾节点，保证其在下一个比较循环前始终指向新链表的最后一个节点。当两个输入链表中有一个已经全部加入新链表中后，比较循环结束，将剩余的另一个输入链表添加到新链表的尾部，即可完成合并。因为开始创建新链表头结点时必须传入参数，所以需要返回头结点的下一个节点作为函数返回结果。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        head = tail = ListNode(0)   ##创建头结点和尾节点
        while l1 and l2:            ##当传入的两个链表l1,l2都不为空时循环
            if l1.val < l2.val:     ##如果l1的值小于l2的值，则让尾节点的next指针指向l1，并更新l1，使其等于自己的下一个节点
                tail.next = l1
                l1 = l1.next
            else:                   ##如果l1的值大于等于l2的值，则让尾节点指向l2，并更新l2，使其等于自己的下一个节点
                tail.next = l2
                l2 = l2.next
            tail = tail.next        ##每次条件判断结束后更新tail，使其等于自己的下一个节点，即保证下一个循环开始前tail为尾节点
        tail.next = l1 or l2        ##循环结束后，l1或l2中必有一个已经全部按序加入新链表，即l1或l2中存在一个空节点，这时使tail的next指针指向l1和l2中非空的节点即可
        return head.next            ##此时头结点为ListNode（0），需要返回head.next作为函数返回值

3.2 使用递归的方法：

基本思路是递归修改next指针。从头结点开始，比较l1和l2结点的值，将值较小的那个节点的next指向递归节点。这个递归节点可以看成一个不断动态变化的链表，这个动态链表的尾节点一直在寻找剩余节点中值最小的节点，让这个剩余节点中值最小的节点尾接到动态链表的屁股后面作为新的尾节点，然后继续递归寻找，直到某个尾节点是某个输入链表的最后一个节点，此时再递归寻找只能是另一个输入链表的节点，所以这时需要返回另一个输入链表的剩余链表的头结点作为递归结果，再层层传递回开始的头结点next指针。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        if not l1 or not l2:
            return l1 or l2
        if l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2