[Leetcode] 合并两个有序数组、链表_合并两个有序链表不申请额外空间

1.合并两个有序数组

原地合并数组，即不使用额外的空间 --> 使用三个指针，从尾部往前处理

题目链接：https://leetcode.cn/problems/merge-sorted-array/

nums1 总长度 m+n，自身长度m；nums2 自身长度n， 使用三个指针，分别执行三个长度的最后

p1 初始指向 nums1有效长度的尾部，p3初始指向nums1的尾部

p2 初始指向 nums2的尾部

输入和最终的数组都是非递减排序，比较 p1 和 p2 所指元素大小，较大者的存到 p3 所指位置，然后指向较大者的指针 和 p3 往前移动一位

如果 p1 或 p2 有一个指针走到了数组的开头，该指针停止移动。之后省去比较步骤，继续把没走完的指针所指值依次存放到 p3 所指位置，同时二指针继续往前移动

Python3

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
 
        # 使用三个指针，分别执行三个长度的最后
        p1_tail, p2_tail = m - 1, n - 1
        tail = m + n - 1
 
        # p1 和 p2 分别遍历完各自的数组，循环才结束
        while p1_tail >= 0 or p2_tail >= 0:
 
            # 如果p1走到头
            if p1_tail == -1:
                nums1[tail] = nums2[p2_tail]
                p2_tail -= 1
            
            # 如果p2走到头
            elif p2_tail == -1:
                nums1[tail] = nums1[p1_tail]
                p1_tail -= 1
 
            # 如果p1位置的值大于p2位置的值，赋值、移动p1
            elif nums1[p1_tail] > nums2[p2_tail]:
                nums1[tail] = nums1[p1_tail]
                p1_tail -= 1
 
            # 如果p2位置的值大于p1位置的值，赋值、移动p2
            else:
                nums1[tail] = nums2[p2_tail]
                p2_tail -= 1
            
            # 上述选择分支已给 p3 所值位置赋值，此处往前移动 p3
            tail -= 1

2.合并两个有序链表

方法一：递归

方法二：虚拟一个起始节点 + 迭代

题目链接：https://leetcode.cn/problems/merge-two-sorted-lists/

方法一：虚拟一个prehead节点

从两个链表中不断找到较小者链上，最后返回 prehead.next

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if not list1:
            return list2
        elif not list2:
            return list1
        else:
            prehead = ListNode(-1)
            pre = prehead
            while list1 and list2:
                if list1.val < list2.val:
                    pre.next = list1
                    list1 = list1.next
                else:
                    pre.next = list2
                    list2 = list2.next
                pre = pre.next
            pre.next = list1 if list1 is not None else list2
            return prehead.next

方法二：递归

把问题转换为找到 list1 和 list2 头节点的较小者（将其指向后续的链表x），从 list1 或 list2 中抽离该节点，解决新链表和另一个链表的相同问题（假设得到链表 x）

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if not list1:
            return list2
        elif not list2:
            return list1
        else:
            if list1.val < list2.val:
                list1.next = self.mergeTwoLists(list1.next,list2)
                return list1
            else:
                list2.next = self.mergeTwoLists(list1,list2.next)
                return list2