链表4：合并有序链表的3道题_有序链表合并算法题

看了这篇文章之后，你会发现LeetCode就是在造题。

一.造题

LeetCode21 和23又是逐步拔高的题目，刷完这两道题，你会发现第1669根本不用刷。为啥呢，我们先看要求：
LeetCode21 ：将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

LeetCode23：合并K个升序链表。给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。

然后再看：

LeetCode1669题：给你两个链表 list1 和 list2 ，它们包含的元素分别为 n 个和 m 个。请你将 list1 中第 a 个节点到第 b 个节点删除，并将list2 接在被删除节点的位置。

1669题的意思就是将list1中的[a,b)区间的删掉，然后将list2接进去，你觉得难吗？如果这也是算法的话，我至少可以造出七八道题，例如：

（1）定义list1的[a,b)区间为list3，将list3和list2按照升序合并成一个链表。

（2）将list2也将区间[a,b)的元素删掉，然后将list1和list2合并成一个链表。

（3）定义list2的[a,b)区间为list4，将list2和list4合并成有序链表。

看到了吗？掌握基础是多么重要，我们自己都能造出题目来。

这也是为什么算法会越刷越少，因为到后面会发现套路就这么写，花样随便换，以不变应万变就是我们的宗旨。

二.合并两个有序链表

这种题有两种类型，一种是新建一个链表，另外一个就是这里的将一个合并到另外一个去，难度都不大，根据题目要求写就行了。

（1）基本写法

public ListNode mergeTwoLists (ListNode list1, ListNode list2) {     // write code here     ListNode newHead=new ListNode(-1);     ListNode res=newHead;     while(list1!=null||list2!=null){ //这么写，减少while的数量，可能耗时会小一些                  if(list1!=null&&list2!=null){//都不为空的情况             if(list1.val<list2.val){                 newHead.next=list1;                 list1=list1.next;             }else if(list1.val>list2.val){                 newHead.next=list2;                 list2=list2.next;             }else{ //相等的情况，分别接两个链                 newHead.next=list2;                 list2=list2.next;                 newHead=newHead.next;                 newHead.next=list1;                 list1=list1.next;             }             newHead=newHead.next;         }else if(list1!=null&&list2==null){             newHead.next=list1;             list1=list1.next;             newHead=newHead.next;         }else if(list1==null&&list2!=null){             newHead.next=list2;             list2=list2.next;             newHead=newHead.next;         }     }     return res.next; }}

（2）适合面试的写法

这个题都多种写法的，上面的都写在一个大while循环里了，看上去有点臃肿，我们可以将其拆开，第一个while只处理两个list 都不为空。之后判断list1和list2哪个不为空就接到合并后的list后面就行了，循环都不用写，也就是这样：

class Solution {    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {        ListNode prehead = new ListNode(-1);​        ListNode prev = prehead;        while (l1 != null && l2 != null) {            if (l1.val <= l2.val) {                prev.next = l1;                l1 = l1.next;            } else {                prev.next = l2;                l2 = l2.next;            }            prev = prev.next;        }        // 最多只有一个还未被合并完，直接接上去就行了        prev.next = l1 == null ? l2 : l1;        return prehead.next;    }} 

 （3）能够给面试官下马威的写法

大部分面试官可能也只知道前面得写法，不见得一下子明白如何通过递归来做。如果面试的时候遇到了，建议先用（2）的写法写出来，面试官满意之后，接着说“我还可以用递归的方式解决这个问题”。

递归我们后面还会分析，这里先简单看一下思想。当我们将list1或者list2中拿到最小的那个结点之后，剩下的不管是list1还是list2都还是完整的链表，而且执行一样的判断逻辑，所以我们就可以通过递归的方式来继续处理：

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个链表

合并k个链表，有多种方式，如果面试，我倾向的方式是先将前两个合并，之后再将后面的逐步合并进来，因为这样的话，我只要将两个合并的写清楚就行了，也就是直接调用二中的方法：

class Solution {    public ListNode mergeKLists(ListNode[] lists) {        ListNode res = null;        for (ListNode list: lists) {            res = merge2Lists(res, list);        }        return res;    }}

四.leetcode1669题

遍历找到链表1保留部分的尾节点和链表2的尾节点，将两链表连接起来。

class Solution {    public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {        ListNode pre1 = list1, post1 = list1, post2 = list2;        int i = 0, j = 0;        while(pre1 != null && post1 != null && j < b){            if(i != a - 1){                pre1 = pre1.next;                i++;            }             if(j != b){                post1 = post1.next;                j++;            }         }        post1 = post1.next;        //寻找list2的尾节点        while(post2.next != null){            post2 = post2.next;        }        //链1尾接链2头，链2尾接链1后半部分的头        pre1.next = list2;        post2.next = post1;        return list1;    }}