合并有序链表

﹏ヽ暗。殇╰゛Y 2022-12-03 15:49 176阅读 0赞

# 合并有序链表 #

## 1、参考资料 ##

https://www.nowcoder.com/practice/a479a3f0c4554867b35356e0d57cf03d

## 2、题目要求 ##

将两个有序的链表合并为一个新链表，要求新的链表是通过拼接两个链表的节点来生成的，即不开辟新的内存空间

## 3、代码思路 ##

首先，为了方便操作链表，我们定义一个 `dummyHead`，我们遍历两个链表，直到其中有一个到达尾部，则停下来

在遍历的过程中，我们将元素值小的节点依次链在 `mergerList` 的后边，最后，我们看看哪个链表还有剩余的节点，将其链在 `mergeList` 的后边，最后返回合并链表的首节点

## 4、代码实现 ##

代码

static class Solution {
        
        /**
         * 合并两个有序链表
         *
         * @param list1 ListNode类
         * @param list2 ListNode类
         * @return ListNode类
         */
        public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        
            ListNode dummyHead = new ListNode(0); // 合并后链表的头结点
            ListNode mergeListPointer = dummyHead; // 合并链表的指针
            ListNode list1Poniter = list1; // list1 的指针
            ListNode list2Poniter = list2; // list2 的指针
    
            // 任意一个链表到尾部，则停止循环
            while (list1Poniter != null && list2Poniter != null) {
        
                // 将小的元素接到 mergeList 的后面
                if (list1Poniter.val < list2Poniter.val) {
        
                    mergeListPointer.next = list1Poniter;
                    list1Poniter = list1Poniter.next; // 指针后移
                } else {
        
                    mergeListPointer.next = list2Poniter;
                    list2Poniter = list2Poniter.next; // 指针后移
                }
                mergeListPointer = mergeListPointer.next; // 指针后移
            }
            // 看看哪个链表还有剩余的部分，将它接在 mergeList 的后面
            if (list1Poniter != null) {
        
                mergeListPointer.next = list1Poniter;
            } else {
        
                mergeListPointer.next = list2Poniter;
            }
            // 返回合并后链表的首结点
            return dummyHead.next;
        }
    }
    
    
    static class ListNode {
        
        int val;
        ListNode next = null;
    
        public ListNode(int val) {
        
            this.val = val;
        }
    }