1 链表结构  

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

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

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

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

链表的缺点:

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

归并排序(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