剑指Offer编程题-合并两个排序的链表 | 我的个人生活记录

题目：合并两个排序的链表

题目描述：输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

解题思路

• 递归：首先根据两个链表头较小的那个作为头结点phead，较小结点的下一个结点与较大结点再次比较返回的结点作为pHead的下一个结点，即pHead.next = self.Merge(pHead.next, pBig)，如果小结点没有下一个结点，那么pHead = pBig，直接与剩下的大结点连接。
• 循环：首先找出头结点，然后定义pSmall、pBig、pTemp三个指针，每一次比较时，如果pSmall的值小于等于pBig的值，pTemp保存pSmall当前结点，然后pSmall = pSmall.next前移，如果pSmall的值大于pBig的值，那么这时pSmall的前一段即pTemp就要接在pBig的后面，pSmall和pBig互换位置继续比较，直到pSmall为空循环结束，pBig可能会剩一些大结点，直接让pTemp指向pBig即可。

实现

python

递归：

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        # write code here
        if not pHead1:
            return pHead2
        if not pHead2:
            return pHead1
        pHead = pHead1 if pHead1.val <= pHead2.val else pHead2
        pBig = pHead2 if pHead1.val <= pHead2.val else pHead1
        pHead.next = self.Merge(pHead.next, pBig) if pHead.next else pBig
        return pHead

python

循环：

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        # write code here
        if not pHead1:
            return pHead2
        if not pHead2:
            return pHead1
        pHead = pHead1 if pHead1.val <= pHead2.val else pHead2
        pSmall = pHead
        pBig = pHead2 if pHead1.val <= pHead2.val else pHead1
        pTemp = pSmall
        while pSmall:
            if pSmall.val > pBig.val:
                pTemp.next = pBig
                pTemp = pBig
                pBig = pSmall
                pSmall = pTemp
            pTemp = pSmall
            pSmall = pSmall.next
        pTemp.next = pBig
        return pHead