剑指offer-16、合并两个有序链表

文章剑指offer-16、合并两个有序链表分享给大家，欢迎收藏Java资料网，专注分享技术知识

题⽬描述

输⼊两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满⾜单调不减规则。

如输⼊{1,3,5} , {2,4,6} 时，合并后的链表为{1,2,3,4,5,6} ，所以对应的输出为{1,2,3,4,5,6} ，转换过程如下图所示：

思路及解答

迭代法（双指针）

使用两个指针分别遍历两个链表，比较当前节点的值，将较小的节点连接到结果链表上。当一个链表遍历完后，将另一个链表的剩余部分直接连接到最后。

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;
    }
    
    // 连接剩余部分
    current.next = (l1 != null) ? l1 : l2;
    
    return dummy.next;
}

• 时间复杂度​：O(n+m)，n和m分别是两个链表的长度
• ​空间复杂度​：O(1)，只使用了固定数量的指针

递归比较

利用递归将问题分解：每次比较两个链表的头节点，选择较小的节点作为合并后链表的头节点，然后递归地合并剩余部分。

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if (l1 == null) return l2;
    if (l2 == null) return l1;
    
    if (l1.val <= l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
}

• 时间复杂度​：O(n+m)，每个节点都会被访问一次
• ​空间复杂度​：O(n+m)，递归调用栈的深度

文章来源:https://www.cnblogs.com/seven97-top/p/19001420
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：jacktools123@163.com进行投诉反馈，一经查实，立即删除！