NC+LC：合并有序数组与链表

前提：以下代码和思路都是根据按从小到大顺序排序的有序数组和链表进行编写的，其他顺序的做法类似。

合并两个有序数组

题目地址

NC22 合并两个有序数组

LC 88.合并两个有序数组：https://leetcode-cn.com/problems/merge-sorted-array/

题目描述

给出两个有序的整数数组 $A \$ 和 $B\$ ，请将数组 $B\$ 合并到数组 $A\$ 中，变成一个有序的数组
注意：可以假设 $A\$ 数组有足够的空间存放 $B\$ 数组的元素， $A\$ 和 $B\$ 中初始的元素数目分别为 $m\$ 和 $n$

思路

设置两个尾指针a和b，获得合并数组的最后一个元素的位置下标index，即n+m-1
从末尾开始比较数组A和B的元素，大的就放到合并数组的末尾，即下标index的位置，因为两个数组是从小到大的顺序，所以通过尾部的比较可以确定合并之后值较大的元素
同时index减一且相应数组上的指针向前移动一位
若A数组没有遍历完，则剩下的元素保持原来的位置；若B数组没有遍历完，则按顺序继续放入

实现代码

public class Solution {
    public void merge(int A[], int m, int B[], int n) {
        int a = m - 1;
        int b = n - 1;
        int index = n + m - 1;//合并数组的最后一个元素位置
        while(a >= 0 && b>=0){
            if(A[a] > B[b]){//从末尾开始比较AB的元素，大的就放入index，对应数组指针移动
                A[index--] = A[a--];
            }else{
                A[index--] = B[b--];
            }
        }
        while(b>=0){//B没有遍历完，直接放入，若A没遍历完的，保持位置即可
            A[index--] = B[b--];
        }
        
    }
}

合并两个有序链表

题目地址

NC33 合并有序链表

LC 21.合并两个有序链表：https://leetcode-cn.com/problems/merge-two-sorted-lists/

解法一：迭代

思路

思路与合并有序数组类似，但链表需要从头开始遍历比较
设置了一个辅助头结点，将排序好的结点进行接入，辅助头结点的next就是我们需要的新链表的头结点
因为是从头开始比较，所以值小的结点先进行接入
若一个链表接入完另一个没有接入完，另一个链表无需再比较直接进行接入

实现代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        ListNode h1 = l1;
        ListNode h2 = l2;
        ListNode curr = new ListNode(-1); //辅助头节点
        ListNode pre = curr;
        while(h1 != null && h2 != null){
            if(h1.val < h2.val){ //小的节点就先接到新链表上
                curr.next = h1;
                h1 = h1.next;
            }else{
                curr.next = h2;
                h2 = h2.next;
            }
            curr = curr.next;
        }
        curr.next = h1 != null ? h1 : h2; //没有遍历完的链表直接接到新链表后面
        return pre.next;
    }
}

解法二：递归

思路

如果 l1 或者 l2 一开始就是空链表，那么没有任何操作需要合并，所以我们只需要返回非空链表。否则，我们要判断 l1 和 l2 哪一个链表的头节点的值更小，然后递归地决定下一个添加到结果里的节点。如果两个链表有一个为空，递归结束。

实现代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) { //递归
        if(l1 == null){
            return l2;
        }else if(l2 == null){
            return l1;
        }else if(l1.val < l2.val){
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        }else{
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}

合并k个已排序的链表

题目地址

NC51 合并k个已排序的链表

LC 23.合并K个升序链表：https://leetcode-cn.com/problems/merge-k-sorted-lists/

解法一：逐个合并

遍历链表数组或集合逐个合并，时间复杂度较大

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists == null || lists.length == 0){
            return null;
        }
        ListNode res = new ListNode(-1); //结果节点
        res.next = lists[0]; //先让结果节点指向第一个链表头节点
        for(int i = 1; i < lists.length; i++){ //遍历链表数组，不断与得到的结果链表进行合并
            ListNode l1 = lists[i];
            ListNode l2 = res.next;
            ListNode l3 = new ListNode(-1);//辅助头节点
            ListNode pre = l3;
            while(l1 != null && l2 != null){ //合并链表
                if(l1.val < l2.val){
                    l3.next = l1;
                    l1 = l1.next;
                }else{
                    l3.next = l2;
                    l2 = l2.next;
                }
                l3 = l3.next;
            }
            l3.next = l1 != null ? l1 : l2; //没有遍历完的链表直接接到新链表后面
            res.next = pre.next; //更新结果节点
        }
        return res.next;
    }
}

解法二：分治合并

分治法，分而治之，在回溯的过程中不断合并，也可运用于排序

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists == null || lists.length == 0){
            return null;
        }
        return merge(lists, 0, lists.length - 1);
    }

    public ListNode merge(ListNode[] lists, int left, int right){ //分治
        if(left == right){
            return lists[left];
        }
        int mid = left + (right - left) / 2;
        ListNode l1 = merge(lists, left, mid);
        ListNode l2 = merge(lists, mid + 1, right);
        return mergeTwoLists(l1, l2);
    }

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) { //通过递归合并两个有序链表
        if(l1 == null){
            return l2;
        }else if(l2 == null){
            return l1;
        }else if(l1.val < l2.val){
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        }else{
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}