剑指offer：合并两个排序的链表 Python | 递归算法、sqrt()函数排序

#coding:utf-8
###1 链表
##1.4 题17 合并两个排序的链表
##题目：输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表蛮族单调不减规则

#关于链表：
# class ListNode:
#     def __init__(self, x):
#         self.val = x # val表示value
#         self.next = Node # next表示指针

#方法一：递归
class Solution:
    def Merge(self, pHead1, pHead2):
        merged = None
        if pHead1 is None: #两个链表是否为空的情况
            return pHead2
        if pHead2 is None:
            return pHead1
        if pHead1.val < pHead2.val : #在两个链表第一个位置找较小的值，对应的值放在merged中，
            # 同时merged和原较小值所在那个链表指针都向后移一位
            merged = pHead1
            merged.next = self.Merge(pHead1.next, pHead2)
        else:
            merged = pHead2
            merged.next = self.Merge(pHead1, pHead2.next)
        return merged

#方法二：非递归
class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        # write code here
        #初始化
        tmp = ListNode(0)
        pre = tmp #此时pre和tmp都属于0这个结点
        while pHead1 and pHead2:
            if pHead1.val < pHead2.val:
                #老鹰捉小鸡三步骤：
                tmp.next = pHead1 #tmp指针指向pHead1（老鹰拽住母鸡背后的小鸡）
                pHead1 = pHead1.next #pHead1指针后移（母鸡往旁边走，完全暴露出小鸡，小鸡孤立无援）
                tmp = tmp.next #tmp跟上，指针后移得到pHead1之前的那个位置的值（老鹰直接抓过来失去保护的小鸡）
            else:
                tmp.next = pHead2
                pHead2 = pHead2.next
                tmp = tmp.next
        if pHead1 is None:
            tmp.next = pHead2
        if pHead2 is None:
            tmp.next = pHead1
        return pre.next

#方法三：sqrt()函数
class Solution:
    def Merge(self, pHead1, pHead2):
        # write code here
        l = []
        while pHead1:
            res.append(pHead1.val)
            pHead1 = pHead1.next
        while pHead2:
            res.append(pHead2.val)
            pHead2 = pHead2.next
        l.sort() #列表从小到大排序
        #初始化
        tmp = ListNode(0) #随便加一个值0放在第一个位置
        pre = tmp
        for i in res:
            list_node = ListNode(i) #定义变量list_node存放列表中的元素作为新链表（单元素）
            tmp.next = list_node
            tmp = list_node
        return pre.next #从第二个位置开始返回

剑指offer上的思路图：