算法通关村第一关——链表经典问题之合并有序链表

柔光的暖阳◎ 2024-03-22 20:59 73阅读 0赞

### 合并两个链表 ###

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

> 将两个有序链表合并为一个新的升序链表并返回，新链表是通过拼接给定的两个链表的所有节点组成的

#### 解决思路 ####

> 思路1：新建一个链表，然后分别遍历两个链表，每次都选最小的节点接到新的链表上，最后排完。
> 
> 要点1：两个链表的长度是不确定的，所以在遍历的时候需要对链表长度进行判断，即如果两个链表长度都相等，进行第一种判断；如果两个链表有一个链表长度比较长，则要将长的链表添加在新链表的后面
> 
> 要点2：因为题目要求最后生成的链表需要是升序的，所以在将两个链表节点存储新的链表时，需要将两个链表较小的元素进行保存

#### 代码实现 ####

/**
         * 思路: 新建一个链表，然后分别遍历两个链表，每次都选最小的结点接到新链表上，最后排完
         * @param headA 链表A
         * @param headB 链表B
         * @return 新链表的头节点
         */
        public Node mergeTwoLists(Node headA , Node headB){
            Node newNode = new Node(-1);
            Node res = newNode;
            // 遍历两个链表
            while (headA != null || headB != null){
                // 情况1 ： 两个链表都不为空
                if (headA != null && headB != null){
                    // 比较两个链表的元素，将小的链表放入新的链表中
                    if (headA.data > headB.data){
                        newNode.next = headB;
                        headB = headB.next;
                    }else if (headA.data < headB.data){
                        newNode.next = headA;
                        headA = headA.next;
                    }else{
                        // 表示链表A和链表B的元素大小相等，这时需要分别连接两个链
                        newNode.next = headA;
                        headA = headA.next;
                        newNode = newNode.next;
                        newNode.next = headB;
                        headB = headB.next;
                    }
                    newNode = newNode.next;
                }
                // 情况2 ： 有一个链表较长，遍历完一个编标后还未为空，将其元素继续连接在新链表中
                else if (headA != null && headB == null){
                    newNode.next = headA;
                    headA = headA.next;
                    newNode = newNode.next;
                }else if (headA == null && headB != null){
                    newNode.next = headB;
                    headB = headB.next;
                    newNode = newNode.next;
                }
            }
            return res.next;
        }

> 思路2：将一个链表节点拆下来，逐个合并到另一个对应位置上去

####  ####

### 合并K个链表 ###

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

> 将K个链表合并为一个链表

#### 解决思路 ####

> 先将两个链表进行合并，然后通过循环逐步将后面的链表进行合并

#### 代码实现 ####

/**
         * 合并K个链表
         * 思路： 先将两个链表进行合并，然后通过循环逐步将后面的链表进行合并
         * @param lists 多个链表头节点
         * @return 新的链表
         */
        public Node mergeKList(Node[] lists){
            Node res = null;
            for (Node list : lists) {
                res = mergeTwoLists(res, list);
            }
            return res;
        }

### 删除节点并拼接 ###

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

> 给俩个链表list1和list2，它们包含的元素分别为n个和m个。请你将list1中下标从a到b的节点删除，并肩list2接在被删除的节点的位置

#### 解决思路 ####

> 题目的意思是将list1中的\[a,b\]区间的元素全部删掉，然后将剩余元素的最后一个元素接入list2。因此只要遍历找到链表1 保留部分的尾节点和链表2 的尾节点，将连个链表连接起来就行。

#### 图解 ####

#### ![e7ab0022b6164b92a6f7c7807d9a90c5.png][] ####

#### 代码实现 ####

/**
         * 给俩个链表list1和list2，它们包含的元素分别为n个和m个。请你将list1中下标从a到b的节点删除，并肩list2接在被删除的节点的位置 
         * @param list1 第一个链表
         * @param a 区间开始的位置
         * @param b 区间结束的位置
         * @param list2 第二个链表
         * @return 新链表头节点
         */
       public Node mergeInBetween(Node list1 , int a ,int b, Node list2){
            Node pre1 = list1;
            Node post1 = list1;
            Node post2 = list2;
    
            int i = 0 , j = 0;
            while (pre1 != null  &&  post1 != null && j<b){
                // 寻找到a的前一个位置
                if (i != a-1){
                    pre1 = pre1.next;
                    i++;
                }
                // 寻找到b的位置
                if (j != b){
                    post1 = post1.next;
                    j++;
                }
            }
            // 链表1链尾 向后移
            post1 = post1.next;
    
            // 找到链2 的尾部
            while (post2.next != null){
                post2 = post2.next;
            }
    
            // 链1 的头 接 链2 的头
           pre1.next = list2;
            // 链2  的尾 接链1 的头
           post2.next = post1;
    
           return list1;
       }

####  ####

[e7ab0022b6164b92a6f7c7807d9a90c5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/a2d67fcd4583453e81b2d3ad8c224c89.png