在Java中合并两个链表

可以使用迭代或递归的方式来实现。以下是两种方法的示例代码：

迭代方法：

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

public class MergeLinkedList {
    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;
    }
}

使用示例：

ListNode l1 = new ListNode(1);
l1.next = new ListNode(2);
l1.next.next = new ListNode(4);

ListNode l2 = new ListNode(1);
l2.next = new ListNode(3);
l2.next.next = new ListNode(4);

MergeLinkedList merger = new MergeLinkedList();
ListNode mergedList = merger.mergeTwoLists(l1, l2);

递归方法：

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

public class MergeLinkedList {
    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;
        }
    }
}

使用示例：

ListNode l1 = new ListNode(1);
l1.next = new ListNode(2);
l1.next.next = new ListNode(4);

ListNode l2 = new ListNode(1);
l2.next = new ListNode(3);
l2.next.next = new ListNode(4);

MergeLinkedList merger = new MergeLinkedList();
ListNode mergedList = merger.mergeTwoLists(l1, l2);

以上代码示例中，我们定义了一个ListNode类来表示链表节点，然后实现了一个MergeLinkedList类来合并两个链表。迭代方法使用一个虚拟头节点dummy和一个指针current来遍历两个链表，比较节点值大小并逐个连接节点。递归方法则通过递归调用来合并链表，每次选择较小的节点连接，并不断向后移动。

这两种方法都能够在时间复杂度为O(n)的情况下合并两个有序链表，其中n是两个链表的总长度。在实际应用中，可以根据具体需求选择合适的方法来实现链表合并。

腾讯云相关产品和产品介绍链接地址：

云服务器 CVM：提供弹性计算能力，满足各类业务需求。
云数据库 MySQL：高性能、可扩展的关系型数据库服务。
云原生容器服务 TKE：基于 Kubernetes 的容器服务，用于快速构建、部署和管理容器化应用。
人工智能平台 AI Lab：提供丰富的人工智能算法和模型，帮助开发者构建智能应用。
物联网开发平台 IoT Explorer：提供全面的物联网设备接入、数据管理和应用开发能力。
移动应用开发平台 MTA：提供移动应用数据分析、推送、统计等功能，助力移动应用开发和运营。
对象存储 COS：安全、稳定、低成本的云端存储服务。
区块链服务 BCOS：提供高性能、可扩展的区块链服务，支持多种应用场景。
腾讯云元宇宙解决方案：基于云计算和人工智能技术的虚拟现实和增强现实解决方案。

请注意，以上链接仅供参考，具体产品选择应根据实际需求进行评估和决策。

页面内容是否对你有帮助？

有帮助

没帮助

扫码

添加站长进交流群

领取专属 10元无门槛券

手把手带您无忧上云

在Java中合并两个链表

相关·内容

【剑指Offer】25. 合并两个排序的链表

Java零基础-299-多态在开发中的作用

day20_常用类/24-尚硅谷-Java语言高级-Java中两个Date类的使用

day20_常用类/24-尚硅谷-Java语言高级-Java中两个Date类的使用

day20_常用类/24-尚硅谷-Java语言高级-Java中两个Date类的使用

Java零基础-300-总结多态在开发中的作用

57_尚硅谷_大数据JavaWEB_在Java中操作JSON.avi

day17_项目三/08-尚硅谷-Java语言基础-项目三NameListService中两个方法及TeamException的完成

day17_项目三/08-尚硅谷-Java语言基础-项目三NameListService中两个方法及TeamException的完成

day17_项目三/08-尚硅谷-Java语言基础-项目三NameListService中两个方法及TeamException的完成

PS使用教程：如何在Photoshop中合并可见图层？

day18_IDEA的使用与多线程/14-尚硅谷-Java语言高级-创建过程中两个问题的说明

扫码

相关资讯

热门标签

活动推荐

运营活动

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐