合并有序数组【刷题记录】

小半 • 2023年2月13日上午9:31 • 技术随笔 • 阅读 244

一、题目描述

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

示例1
输入：
{1,3,5},{2,4,6}
复制
返回值：
{1,2,3,4,5,6}

二、解题思路

1、把结果用列表存放再返回
2、用递归方法，不断进行比较合并返回

三、解题代码

设置临时数组temp用于存储合并的数组，代码如下：

class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        # write code here
        head = ListNode(0)
        tmp = head
        while pHead1 is not None and pHead2 is not None:
            if pHead1.val <= pHead2.val:
                tmp.next = pHead1
                pHead1 = pHead1.next
            else:
                tmp.next = pHead2
                pHead2 = pHead2.next
            tmp = tmp.next
             
        if pHead1 is None:
            tmp.next = pHead2
        elif pHead2 is None:
            tmp.next = pHead1
             
        return head.next

上边注释版：

class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        # write code here
        head = ListNode(0)  #新建一个头结点
        tmp = head  #防止链表断开头，设置临时结点，便于指定后续节点
        while pHead1 is not None and pHead2 is not None:
            if pHead1.val <= pHead2.val: #比较两个链表pHead1、pHead2当前节点大小
                tmp.next = pHead1 #合并后链表节点指向较小值得结点
                pHead1 = pHead1.next #pHead1继续往后移动
            else:
                tmp.next = pHead2 
                pHead2 = pHead2.next  #pHead2继续往后移动
            tmp = tmp.next #每一步，都需将合并后链表继续往后移动
             
        if pHead1 is None:
            tmp.next = pHead2 #当pHead1为空即尾结点时，合并后链表指向另一链表进行继续排序和移动
        elif pHead2 is None:
            tmp.next = pHead1
        return head.next  #最后，返回合并后链表的后续节点即头节点

others:

class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        # write code here
        if not pHead1:
            return pHead2
        if not pHead2:
            return pHead1
        pMerge = None
        if pHead1.val <= pHead2.val:
            pMerge = pHead1
            pMerge.next = self.Merge(pHead1.next, pHead2)
        else:
            pMerge = pHead2
            pMerge.next = self.Merge(pHead1, pHead2.next)
        return pMerge