[Java·算法·中等] LeetCode21. 合并两个有序链表

人不走空

发布于 2024-03-23 09:23:27

920

发布于 2024-03-23 09:23:27

文章被收录于专栏：学习与分享学习与分享

题目

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

示例

示例1

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例2

输入：l1 = [], l2 = []
输出：[]

示例3

输入：l1 = [], l2 = [0]
输出：[0]

提示

👉️ 力扣原文

/**
 * 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 {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1==null){
            return list2;
        }
        else if(list2==null){
            return list1;
        }
        else if(list2.val > list1.val){
            list1.next = mergeTwoLists(list1.next,list2);
            return list1;
        }
        else{
            list2.next = mergeTwoLists(list1,list2.next);
            return list2;
        }


    }
}

详细解读

这段代码实现了合并两个升序链表的算法。让我们逐步解读：

首先，创建一个名为dummy的虚拟头结点（dummy node），其值为0。这个dummy节点的作用是为了简化算法的实现，它的下一个节点将指向合并后的链表的头结点。
创建一个名为current的指针，初始化为dummy节点，用于迭代合并后的链表。
在一个while循环中，不断比较两个链表当前节点的值，选取其中较小的节点添加到合并后的链表中。循环的条件是两个链表都不为空。
如果l1的值小于l2的值，则将current的下一个节点指向l1，并将l1指针向后移动一位；否则将current的下一个节点指向l2，并将l2指针向后移动一位。
不断迭代直到其中一个链表到达末尾。
最后，如果其中一个链表还有剩余的节点，则直接将剩余链表接在合并后链表的末尾。
返回dummy节点的下一个节点，即合并后链表的头结点。

这个算法的时间复杂度是O(m + n)，其中m和n分别是两个输入链表的长度，因为它只需遍历每个节点一次。

idea上代码运行

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) {
        this.val = val;
    }
}

public class MergeTwoSortedLists {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        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;
        }
        
        if (l2 != null) {
            current.next = l2;
        }
        
        return dummy.next;
    }
    
    public static void main(String[] args) {
        // Example usage:
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(3);
        l1.next.next = new ListNode(5);
        
        ListNode l2 = new ListNode(2);
        l2.next = new ListNode(4);
        l2.next.next = new ListNode(6);
        
        MergeTwoSortedLists merger = new MergeTwoSortedLists();
        ListNode merged = merger.mergeTwoLists(l1, l2);
        
        // Print the merged list
        while (merged != null) {
            System.out.print(merged.val + " ");
            merged = merged.next;
        }
    }
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2024-03-23，如有侵权请联系 cloudcommunity@tencent.com 删除

java