【DS】链表面试热题之合并链表及其变体

分手后的思念是犯贱 2024-04-03 10:00 96阅读 0赞

##  ##

#### 文章目录 ####

*  
 *   *  一、合并两个有序链表
     *   *  题目描述
         *  思路分析：
         *  图示分析：
         *  AC代码
     *  二、合并k个有序链表
     *   *  题目描述
         *  思路分析：
         *  几点注意：
         *  图示分析：
         *  AC代码

--------------------

*合并有序链表核心思路：*

双指针：分别遍历两个链表，然后链到总的链表上。

--------------------

模板：

ListNode head = new ListNode(-1);
    ListNode prev = head;
    while (list1 != null && list2 != null) {
        
        if (list1.val <= list2.val) {
        
            prev.next = list1;
            list1 = list1.next;
        } else {
        
            prev.next = list2;
            list2 = list2.next;
        }
        prev=prev.next;
    }
    prev.next=(list1==null)?list2:list1;
    return head.next;

--------------------

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

#### 题目描述 ####

1.输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。[OJ链接][OJ]

#### 思路分析： ####

1.  比较两个链表当前引用的val值小的加入总的链，循环比较操作，循环条件是两个引用都不是空的，否则容易空指针异常。
2.  循环终止的时候，肯定有一个结点不是空的这个时候我们需要单独操作，，然后让总的遍历的pre链上它
3.  为了方便操作这里引用了一个虚拟头结点，返回的时候只要返回它的next值即可

#### 图示分析： ####

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-PXbrAMvb-1665134357599)(F:\\typora插图\\image-20221007161646165.png)\]][img-PXbrAMvb-1665134357599_F_typora_image-20221007161646165.png]

#### AC代码 ####

public ListNode Merge(ListNode list1, ListNode list2) {
        
        ListNode head = new ListNode(-1);
        ListNode prev = head;
        while (list1 != null && list2 != null) {
        
            if (list1.val <= list2.val) {
        
                prev.next = list1;
                list1 = list1.next;
            } else {
        
                prev.next = list2;
                list2 = list2.next;
            }
            prev=prev.next;
        }
        prev.next=(list1==null)?list2:list1;
        return head.next;
    }

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

#### 题目描述 ####

2.合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。[OJ链接][OJ 1]

#### 思路分析： ####

1.  给的顺序表，顺序表中的每个值是链表的每个头结点，所以循环条件是顺序表不为空
2.  一个一个从表中拿出来，在调用我们之前定义的合并两个有序链表肯定行不通，这样不满足时间复杂度为O(nlogn)，行不通。

#### 几点注意： ####

1.  注意导包
2.  `int mid = left + (right - left) /2;`可以通过，但是`int mid = left + (right - left)>>1;`没办法通过，原因未知，以后再说。

#### 图示分析： ####

![在这里插入图片描述][dccfb3769ed449c0832887a1028b22b0.gif_pic_center]

#### AC代码 ####

public ListNode mergeKLists(ArrayList<ListNode> lists) {
        
        return divideMergeLists(lists,0,lists.size()-1);
    }
    private ListNode divideMergeLists(ArrayList<ListNode> lists, int left,int right) {
        
        if (left > right) {
        
            return null;
        } else if (left == right) {
        
            return lists.get(left);
        }
        int mid = left + (right - left) /2;
        return Merge(divideMergeLists(lists, left, mid), divideMergeLists(lists, mid+1, right));
    }
    private ListNode Merge(ListNode list1, ListNode list2) {
        
        ListNode head = new ListNode(-1);
        ListNode prev = head;
        while (list1 != null && list2 != null) {
        
            if (list1.val <= list2.val) {
        
                prev.next = list1;
                list1 = list1.next;
            } else {
        
                prev.next = list2;
                list2 = list2.next;
            }
            prev = prev.next;
        }
        prev.next = (list1 == null) ? list2 : list1;
        return head.next;
    }

[OJ]: https://www.nowcoder.com/practice/d8b6b4358f774294a89de2a6ac4d9337?tpId=295&tqId=23267&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
[img-PXbrAMvb-1665134357599_F_typora_image-20221007161646165.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/92014a11501649b38a0f66eaa99dd8a2.png
[OJ 1]: https://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6?tpId=295&tqId=724&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
[dccfb3769ed449c0832887a1028b22b0.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/048b62ea25fc46b7897927aea83b3531.gif