python实现leetcode-第21题-合并两个有序链表

1 链表结构  

链表结构是由许多节点构成的，每个节点都包含两部分：

  数据部分：保存该节点的实际数据。
  地址部分：保存的是下一个节点的地址。
链表的特点:

结点在存储器中的位置是任意的，即逻辑上相邻的数 据元素在物理上不一定相邻
访问时只能通过头指针进入链表，并通过每个结点的 指针域向后扫描其余结点，所以寻找第一个结点和最后一 个结点所花费的时间不等
链表的优点：

数据元素的个数可以自由扩充 、插入、删除等操作不必移动数据，只需 修改链接指针，修改效率较
 

链表的缺点:

存储密度小 、存取效率不高，必须采用顺序存取，即存 取数据元素时，只能按链表的顺序进行访问 
 

2 归并排序（MERGE-SORT）

是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

编写程序时：（参考https://blog.csdn.net/gleam_/article/details/80149010的博客），

注意first与head的不同

注意ListNode的初始化（要加零）

注意None要大写

注意比较的主体是谁

注意返回值

# 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 = ListNode(0)
        first = head
        while l1 != None and l2 != None:
            if l1.val<=l2.val:
                head.next=l1
                l1=l1.next
                head=head.next
            else:
                head.next=l2
                l2=l2.next
                head=head.next
        if l1 != None:
            head.next = l1
        if l2 != None:
            head.next = l2   
        return first.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 l1==None and l2==None:
            return None
        if l1==None:
            return l2
        if l2==None:
            return l1
        if l1.val<=l2.val:
            l1.next=self.mergeTwoLists(l1.next,l2)
            return l1
        else:
            l2.next=self.mergeTwoLists(l1,l2.next)
            return l2