剑指 Offer 25. 合并两个排序的链表及扩展

剑指 Offer 25. 合并两个排序的链表

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
限制：

0 <= 链表长度 <= 1000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof

递归

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
const mergeTwoLists=function(l1,l2){
    if(l1==null){
        return l2;
    }
    if(l2==null){
        return l1;
    }
    if(l1.val<l2.val){
        l1.next=mergeTwoLists(l1.next,l2);
        return l1;
    }else{
        l2.next=mergeTwoLists(l1,l2.next);
        return l2;
    }
};

面试题 10.01. 合并排序的数组

给定两个排序后的数组 A 和 B，其中 A 的末端有足够的缓冲空间容纳 B。编写一个方法，将 B 合并入 A 并排序。

初始化 A 和 B 的元素数量分别为 m 和 n。

示例:

输入:
A = [1,2,3,0,0,0], m = 3
B = [2,5,6], n = 3

输出: [1,2,2,3,5,6]
说明:

A.length == n + m

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sorted-merge-lcci

看起来比较相似，然而想一下应该是用到双指针的

这里我们从两个数组的末尾开始扫描

class Solution:
    def merge(self, A: List[int], m: int, B: List[int], n: int) -> None:
        """
        Do not return anything, modify A in-place instead.
        """
        i,j=m-1,n-1
        cur=m+n-1
        while i>=0 and j>=0:
            if A[i]<B[j]:
                A[cur]=B[j]
                j-=1
            else:
                A[cur]=A[i]
                i-=1
            cur-=1
        if j!=-1:#如果B没扫完，直接丢到A前面
            A[:j+1]=B[:j+1]
        return A

88. 合并两个有序数组

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。

说明:

初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。

示例:

输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3

输出: [1,2,2,3,5,6]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-sorted-array

同理

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        while m>0 and n >0:
            if nums1[m-1]<=nums2[n-1]:
                nums1[m+n-1]=nums2[n-1]
                n-=1
            else:
                nums1[m+n-1]=nums1[m-1]
                m-=1
        if n>0:
            nums1[:n]=nums2[:n]

56. 合并区间

给出一个区间的集合，请合并所有重叠的区间。

示例 1:

输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:

输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-intervals

主要是排序

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        if len(intervals)<=1:
            return intervals
        def get_first(l):
            return l[0]
        intervals.sort(key=get_first)
        res=[intervals[0]]
        for i in range(1,len(intervals)):
            if intervals[i][0]<=res[-1][1]:
                res[-1]=[res[-1][0],max(intervals[i][1],res[-1][1])]
            else:
                res.append(intervals[i])
        return res

23. 合并K个排序链表

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-k-sorted-lists

终于来到进阶版本了，这道题说是hard，其实就是从归并排序（merge sort）演化来的，再＋分治的思想

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        n=len(lists)
        
        #pre-operation
        if n==0:return None
        if n==1:return lists[0]
        if n==2:return self.mergeTwoLists(lists[0],lists[1])
        
        #divid and conquer
        mid=n//2
        return self.mergeTwoLists(self.mergeKLists(lists[:mid]),self.mergeKLists(lists[mid:n]))

    def mergeTwoLists(self,l1:ListNode,l2:ListNode)->ListNode:
        res=ListNode(0)
        q1,q2,q3=l1,l2,res
        while q1 or q2:
            if q1 and q2:
                if q1.val<q2.val:
                    q3.next=ListNode(q1.val)
                    q1=q1.next
                else:
                    q3.next=ListNode(q2.val)
                    q2=q2.next
                q3=q3.next
            elif q1:
                q3.next=q1
                break
            else:
                q3.next=q2
                break
            
        return res.next