Leecode 上面关于合并操作的题目挺有意思的，这里特地总结一下： 遂有此文。

题目

88. 合并两个有序数组 - E (opens new window)

21. 合并两个有序链表 - E (opens new window)

23. 合并K个升序链表 - H (opens new window)

---

1. 88. 合并两个有序数组 (opens new window)

facebook - 68 ,亚马逊 - 9,字节 - 8,微软 - 6

这道题有个技巧就是：非递减，所以从后往前比较是最合适的。

public class Solution{

    public void merge(int[] nums1, int m, int[] nums2, int n) {
         // 非递减顺序
         int index = m + n -1; // 最大值的坐标

         int m1 = m - 1; // 从后往前比较

         int n1 = n - 1; // 从后往前比较

         while(m1 >= 0 && n1 >= 0){
             if(nums1[m1] > nums2[n1]){
                nums1[index --] = nums1[m1 --];
             }else{
                nums1[index --] = nums2[n1 --];
             }
         }

        //注意这里 m 可能小于 n
        while(n1 >= 0){
            nums1[index--] = nums2[n1--];
        }
    }
}

2. 21. 合并两个有序链表 - E (opens new window)

微软 - 14, 字节 - 15, 亚马逊 - 41

递归法：

public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode 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(l2.next,l1);
            return l2;
        }
    }
}

迭代法:

public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null){
            return l2;
        }

        if(l2 == null){
            return l1;
        }

        ListNode head = new ListNode(-1);
        ListNode cur = head;

        while(l1 != null && l2 != null){
            if(l1.val < l2.val){
                cur.next = l1;
                l1 = l1.next;
            }else{
                cur.next = l2;
                l2 = l2.next;
            }

            cur = cur.next;
        }

        if(l1 == null){
            cur.next = l2;
        }else{
            cur.next = l1;
        }
        //注意这里的返回值是 head.next;
        return head.next;
    }
}

3. 23. 合并K个升序链表 - H (opens new window)

本人觉得，要想彻底掌握此类题目，我们需要掌握归并排序 (opens new window)的思想。核心:分而治之。

逐一合并两条链表

分治能减少时间复杂度是基于解决小问题的运算复杂度会小于解决大问题的运算复杂度这一事实，重点在于对求解问题规模的缩减. 分治的时间复杂度为logk，但顺序合并是k

1. 顺序合并两条链表, 时间复杂度：O(NK)

    public ListNode mergeKLists(ListNode[] lists){
        ListNode res = null;
        for(ListNode node:lists){
            res = mergeKLists(res,node);
        }
        return res;
    }

2. 采用分治思想，两两合并.时间复杂度: O(NlogK)

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 n1 = merge(lists,left,mid);
        ListNode n2 = merge(lists,mid+1,right);
        return mergeTwoLists(n1,n2);
    }

    

    // 采用归并思想，先搞定2个有序链表
    public ListNode mergeTwoLists(ListNode n1, ListNode l2){
        
        if(l1 == null){
            return l2;
        }

        if(l2 == null){
            return l1;
        }

        ListNode head = new ListNode(-1);
        ListNode cur = head;

        while(l1 != null && l2 != null){
            
            if(l1.val < l2.val){
                cur.next = l1;
                l1 = l1.next;
            }else{
                cur.next = l2;
                l2 = l2.next;
            }

            cur = cur.next;
        }

        if(l1 == null){
            cur.next = l2;
        }else{
            cur.next = l1;
        }

        return head.next;
    }
}

---

3. 148. 排序链表 (opens new window)

归并排序 (opens new window)最适合用于链表排序。。

归并排序对于数组而言，时间复杂度为O(NlogN),空间复杂度为N,所以不是很完美。但归并排序对于链表来说，空间复杂度为常数。基于其NlogN的时间复杂度以及稳定性。

归并排序运用在链表和数组的原理是相同的。但是基于链表的特性，需要注意以下几点:

1. 使用快慢指针找到链表的中间节点；
2. 找到中间节点后，拆分链表时，需要注意，将mid.next 置为null,否则有可能出现循环链表的情况。

---

这也说明归并不仅仅是一种排序，更重要的是分而治之的思想。

class Solution {
    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        // 1. 获取中间节点
        ListNode mid = findMid(head);
        
        ListNode left = head;
        ListNode right = mid.next;
        // 这一点非常重要,不然可能出现循环链表
        mid.next = null;

        return merget(sortList(left),merge(sortList(right)));
    }

    // 合并链表
    public ListNode merge(ListNode left, ListNode right){
        if(left == null)  return left;
        if(right == null) return right;

        ListNode head = new ListNode(-1);
        ListNode cur = head;

        while(left != null && right != null){
            if(left.val < right.val){
                cur.next = left;
                left = left.next;
            }else{
                cur.next = right;
                right = right.next;
            }
            cur = cur.next;
        }

        if(left != null){
            cur.next = left;
        }else{
            cur.next = right;
        }

        return head.next;
    }

    /**
     * 使用快慢指针快速找到中间节点
     * 这个地方求中间节点(当节点个数为偶数时，求的是前一个节点) 
     */
    public ListNode findMid(ListNode head){
        if(head == null || head.next == null){
            return head;
        }
        ListNode slow = head;
        ListNode fast = head;
        while(fast.next != null && fast.next.next != null){
                fast = fast.next.next;
                slow = slow.next;
        }

        return slow;
    }