剑指Offer 16. 合并两个排序的链表 （链表）

题目描述

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

题目地址

https://www.nowcoder.com/practice/d8b6b4358f774294a89de2a6ac4d9337?tpId=13&tqId=11169&rp=3&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tPage=1

思路

思路1：循环：如果两个链表不为空，进行比较，将小的赋给合并的指针头，小的链表走一步，合并链表走一步，如果有一个为空，跳出循环，并将另一不为空的链表后续部分赋给合并链表

思路2：递归：如果第一个链表为空，则返回第二个链表，如果第二个链表为空，则返回第一个链表，如果两个链表都为空，结果为空

两个链表都是排序好的，我们只需要从头遍历链表，判断当前指针，哪个链表的值小，即赋给合并链表指针。

Python

# -*- coding:utf-8 -*-

class ListNode:

    def __init__(self, x):

        self.val = x

        self.next = None

node1 = ListNode(1)

node2 = ListNode(3)

node3 = ListNode(5)

node1.next = node2

node2.next = node3

node4 = ListNode(2)

node5 = ListNode(4)

node6 = ListNode(6)

node4.next = node5

node5.next = node6

class Solution:

    # 返回合并后列表

    def Merge(self, pHead1, pHead2):

        # 循环

        # newHead = ListNode(-1)

        # pre = newHead

        # while pHead1 and pHead2:

        #     if pHead1.val < pHead2.val:

        #         pre.next = pHead1

        #         pHead1 = pHead1.next

        #     else:

        #         pre.next = pHead2

        #         pHead2 = pHead2.next

        #     pre = pre.next

        # pre.next = pHead1 if pHead1 else pHead2

        # return newHead.next

        # 递归

        if not pHead1:

            return pHead2

        if not pHead2:

            return pHead1

        newHead = None

        if pHead1.val < pHead2.val:

            newHead = pHead1

            newHead.next = self.Merge(pHead1.next, pHead2)

        else:

            newHead = pHead2

            newHead.next = self.Merge(pHead1, pHead2.next)

        return newHead

if __name__ == '__main__':

    result = Solution().Merge(node1,node4)

    print('合并链表：',end = ' ')

    while result:

        print(result.val,end = ' ')

        result = result.next