当前位置：首页 > article >正文

21. 合并两个有序链表

article 2024/10/7 11:02:22

一、问题描述

二、解题思路

三、代码

四、复杂度分析

一、问题描述

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

二、解题思路

要将两个升序链表合并为一个新的升序链表，本质上是一个归并排序中的合并两个有序数组的思路。由于链表的节点是通过指针连接的，因此不需要创建新的节点，只需要适当调整原链表节点的 next 指针即可。

具体步骤

创建虚拟头节点：为了简化操作（尤其是头节点的处理），我们创建一个虚拟头节点 dummy，并且使用一个指针 current 来指向新链表的最后一个节点，初始时指向 dummy。
遍历两个链表：
- 比较两个链表的当前节点的值，选择较小的节点，将其接到 current 节点之后，然后将当前链表的指针移动到下一个节点。
- 重复此过程，直到其中一个链表为空。
处理剩余节点：
- 当其中一个链表遍历结束后，直接将另一个链表中剩余的节点接到新链表的最后。
返回结果：最后返回 dummy.next，即新链表的头节点。

三、代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    // 函数参数需要包含两个链表 l1 和 l2
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 创建一个虚拟头节点，简化处理逻辑
        ListNode dummy = new ListNode(-1);
        ListNode current = dummy;
        
        // 当两个链表都不为空时，进行遍历
        while (l1 != null && l2 != null) {
            // 比较两个链表当前节点的值
            if (l1.val <= l2.val) {
                // 将较小的节点接到新链表上
                current.next = l1;
                // 移动指针到下一个节点
                l1 = l1.next;
            } else {
                current.next = l2;
                l2 = l2.next;
            }
            // 更新新链表的当前节点指针
            current = current.next;
        }
        
        // 将剩余的链表节点接到新链表上
        if (l1 != null) {
            current.next = l1;
        } else if (l2 != null) {
            current.next = l2;
        }
        
        // 返回新链表的头节点
        return dummy.next;
    }
}