算法面试题：合并有序链表系列（合并两个，合并n个）分治算法

╰+攻爆jí腚メ 2023-10-04 18:41 58阅读 0赞

### 算法面试题：合并有序链表系列（合并两个，合并n个） ###

#### 内容目录 ####

*   *  算法面试题：合并有序链表系列（合并两个，合并n个）
     *   *  一、合并两个有序链表
         *   *  方法1
             *  方法2：
         *  二、合并n个有序链表
         *   *  分治解法：

> 合并有序链表问题，可以分为两种，一种是合并两个有序链表，另一种是合并n个有序链表

#### 一、合并两个有序链表 ####

合并两个链表，可以想到的方法大概分为两种

一种是开辟一个空间，逐渐比较两个链表，小的放到空间中，以此类推

一种是不开辟另外的空间，直接使用list1或者list2

##### 方法1 #####

public ListNode Merge(ListNode list1,ListNode list2) {
        
      if(list1 == null) return list2;
      if(list2 == null) return list1;
      // 开辟一个新空间
      ListNode newHead = new ListNode(-1);
      ListNode ptr = newHead;
      while(list1 != null && list2 != null){
        
          if(list1.val <= list2.val){
        
              ptr.next = list1;
              ptr = ptr.next;
              list1 = list1.next;
          }else{
        
              ptr.next = list2;
              ptr = ptr.next;
              list2 = list2.next;
          }
      }
      ptr.next = (list1 == null) ? list2 : list1;
      return newHead.next;
    }

##### 方法2： #####

public ListNode Merge(ListNode list1,ListNode list2) {
        
      if(list1 == null) return list2;
      if(list2 == null) return list1;
      // 借助list1或者list2空间
      if(list1.val <= list2.val){
        
          list1.next = Merge(list1.next, list2);
          return list1;
      }else{
        
          list2.next = Merge(list1, list2.next);
          return list2;
      }
    }

#### 二、合并n个有序链表 ####

能想到几种方法

首先，最容易想到的，就是把所有的节点放到一个列表中，然后重新构建新链表

另外还可以使用分治算法，n个链表我们不知道怎么合并，但是两个我们知道，所以将n个链表分成两两一组  
![在这里插入图片描述][74162e10f9104d91a6879dabbfa286c1.png]

##### 分治解法： #####

public ListNode mergeKLists(ArrayList<ListNode> lists) {
        
        return mergeList(lists, 0, lists.size() - 1);
    }
    
    // 分治处理，将n个有序链表，变成两个链表的处理
    public ListNode mergeList(ArrayList<ListNode> lists, int L, int R){
        
        // 只有一个链表
        if(L == R) return lists.get(L);
        // 链表集合为空
        if(L > R) return null;
        int mid = L + ((R - L) >> 1);
        return Merge(mergeList(lists, L, mid), mergeList(lists, mid+1, R));
    }
    
    // 两个链表的合并
    public ListNode Merge(ListNode list1, ListNode list2){
        
        if(list1 == null) return list2;
        if(list2 == null) return list1;
        if(list1.val <= list2.val){
        
            list1.next = Merge(list1.next, list2);
            return list1;
        }else{
        
            list2.next = Merge(list1, list2.next);
            return list2;
        }
    }

[74162e10f9104d91a6879dabbfa286c1.png]: https://img-blog.csdnimg.cn/74162e10f9104d91a6879dabbfa286c1.png