开发者社区

文档建议反馈控制台

最新优惠活动

文章/答案/技术大牛

发布

在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：提供高性能、可扩展的区块链服务，支持多种应用场景。
腾讯云元宇宙解决方案：基于云计算和人工智能技术的虚拟现实和增强现实解决方案。

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

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

有帮助

没帮助

相关·内容

合并两个有序链表

JavaScript实现LeetCode第21题：合并两个有序链表题目描述将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。...示例：输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4 思路分析新建一个链表，然后比较两个链表中的元素值，把较小的那个链到新链表中，由于两个输入链表的长度可能不同，所以最终会有一个链表先完成插入所有元素...，则直接另一个未完成的链表直接链入新链表的末尾。

1.6K3 0

合并两个有序链表

合并两个有序链表，使得合并后的结果仍然是有序的，直观的做法就是从两个链表的首节点开始比较，将其中小的那个链接到新链表之中，（如果不想破坏原链表，那么需要将该节点拷贝一份，然后链接到新链表之中。）...} } if (NULL == p1) { p3->Next = p2; } if (NULL == p2) { p3->Next = p1; } //此处在原节点的基础上合并两个链表...，破坏掉了原链表，使得原链表为空 L1->Next = NULL; L2->Next = NULL; //返回新链表的头指针 return p; } 这种使用双指针的方法，不止在合并链表的时候会用到...，前面做删除数组中重复的元素时候，使用了相同的思路，快速排序也使用了类似的方式。...在单链表上插入，删除一个节点，必须知道其前驱节点。线性表是最基本的数据结构，将来树和图都将依赖于线性表来实现。（广义的表结构）

5.1K2 0

合并两个排序链表

题意将两个排序链表合并为一个新的排序链表样例给出 1->3->8->11->15->null，2->null，返回 1->2->3->8->11->15->null。...思路这道题很简单，属于链表的基本操作。只需要创建一个新的链表与一个指向新链表最后一个节点的指针即可。...当 l1 与 l2 均不为空的情况下，判断 l1 和 l2的大小，把较小值放进新链表的最后一个节点，然后将较小值所处的链表向后移一位，以判断下一个数。...依次循环，直到 l1 或 l2 中有一方为空时，将为空的一方，直接加到新链表后即可。代码实现 /** * Definition for ListNode....= l2; if (l2 == null) { lastNode.next = l1; } return listNode.next; } } 原题地址 LintCode：合并两个排序链表

1.5K1 0

【合并两个有序链表】

，用于合并两个已排序的链表。...下面是对这段代码的解释：创建一个哑节点（dummy）作为合并后链表的头部，并创建一个指针 tail 指向 dummy，同时初始化为0。...ListNode* dummy = new ListNode(0); ListNode* tail = dummy; 使用 while 循环遍历两个输入链表 list1 和 list2，进行合并操作，直到其中一个链表为空...，将剩余的非空链表直接连接到合并链表的尾部。...if (list1) { tail->next = list1; } if (list2) { tail->next = list2; } 最后，获取合并后链表的头部节点，删除哑节点，返回合并后的链表

260 0

合并两个有序链表

合并两个有序链表将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 ?...，判断 l1 和 l2 哪一个链表的头节点的值更小，将较小值的节点添加到结果里，当一个节点被添加到结果里之后，将对应链表中的节点向后移一位。...在循环终止的时候， l1 和 l2 至多有一个是非空的。由于输入的两个链表都是有序的，所以不管哪个链表是非空的，它包含的所有元素都比前面已经合并链表中的所有元素都要大。...这意味着我们只需要简单地将非空链表接在合并链表的后面，并返回合并链表即可 /** * Definition for singly-linked list....否则，我们要判断 l1 和 l2 哪一个链表的头节点的值更小，然后递归地决定下一个添加到结果里的节点。如果两个链表有一个为空，递归结束。

1.4K3 0

合并两个排序链表

合并两个排序链表描述将两个排序链表合并为一个新的排序链表样例给出 1->3->8->11->15->null，2->null，返回 1->2->3->8->11->15->null。...那么其实可以比较两个链表当前节点的值,哪个值小,就把它连接在新链表的后面,并将这个链表的当前指针后移一位.知道某一个链表为空,将另一个链表的所有值链接在后面即可....实现代码 public ListNode mergeTwoLists(ListNode l1, ListNode l2) { //由于不知道两个链表哪个头结点大,所以自定义一个头结点 ListNode...dummy = new ListNode(-1), cur = dummy; //当两个链表都不为空 while (l1 !...= null) { //将两个链表中较小的当前节点链接在结果链表上,该链表后移一位 if (l1.val < l2.val) { cur.next = l1; l1

1.5K2 0

两个排序链表合并

Merge Two Sorted Lists 已知两个已排序链表头节点指针L1，L2，将这两个链表合并，合并后仍为有序的，返回合并后的头节点。 ?...最后再连接不为空的那段链表(l1或l2)。 ?

1.4K3 0

合并两个有序链表！

题目描述将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。...吴师兄的思路当 l1 和 l2 都不为空时，判断 l1 和 l2 哪一个链表的头节点的值更小，将较小值的节点添加到结果中，当一个节点被添加到结果中之后，将对应链表中的节点向后移一位，查看和对比下一个节点...具体操作如下： 1、由于需要对比两个链表的头节点，为了让两个原链表的头节点的地位与其它节点的地位一样，避免做其它额外的判断处理，这里设定一个虚拟头节点 dummy ，方便后续返回合并后的链表 2、维护一个...6、在重复 3 和 4 的操作过程中，每操作成功一次，pre 都需要向后移动一位。...它包含的所有元素都比前面已经合并链表中的所有元素都要大。

1.4K8 0

合并两个有序链表

已知两个链表head1和head2各自有序，请把它们合并成一个链表依然有序。结果链表要包含head1和head2的所有节点，即使节点值相同。注意：不能开辟新空间来存储合并后的链表。...2.非递归实现算法过程：输入：两个有序的单链表head1与head2；输出：合并后的有序单链表mergeHead；算法描述：（1）如果head1或head2为空链表，则直接返回另外一个链表...{ curList2->next=newNode2; curList2=curList2->next; } } //合并两个有序链表...7 8 ss1 strIn:3 4 5 6 7 8 合并后链表： 1 2 3 3 4 5 5 6 7 8 3.递归实现从上面合并两个有序链表的步骤中可以看出，每次合并的步骤（2）都是一样的，由此我们想到了递归...mergeOrderedLinkedListRecursion(head1,head2->next); } return mergeHead; } ---- 参考文献 [1]C++算法之合并两个有序链表

2.2K2 1

合并两个有序链表

合并两个有序链表将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。...，p2分别指向两个有序链表的头结点，定义一个指针p3始终指向新链表的最后一个节点，定义一个指针ptmp指向新链表的头结点。...每一次循环都比较两个指针指向节点的值，将偏小的节点加到新链表中（若相等则将p2加到新链表中），且较小的链表上的指针往后移动一位。当p1、p2任意next节点为空时，将非空节点加到新链表中。...图示为： 1.创建链表及指针 2.比较数值大小，把较小的节点加到已排序的链表中 3.将p1指针向后移动 4.将p3移动到已排序链表的最后一个节点 5.同步骤2 6.同步骤3...->将原链表指针向后移动->将新链表指针向后移动当循环结束后，把原链表非空指针指向的节点加到已排序的链表中即可，返回虚拟头结点的next节点，即可得到合并后的有序链表

1612 0

合并两个有序链表(java)

二、题目描述：题目：将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 ...= [1,3,4] 输出：[1,1,2,3,4,4] 示例 2：输入：l1 = [], l2 = [] 输出：[] 示例 3：输入：l1 = [], l2 = [0] 输出：[0] 提示：两个链表的节点数目范围是...合并两个顺序链表，无非就可以采用递归过程建模。根据以上规律考虑本题目，终止条件：当两个链表都为空时，表示我们对链表已合并完成。如何递归？...我们直接判断 l1 和 l2 头结点哪个更小，然后较小结点的 next 指针指向其余结点的合并结果。也就是说，两个链表头部值较小的一个节点与剩下元素的 merge 操作结果合并即可。...其中n 和m 分别为两个链表的长度。空间复杂度：O(n + m)。其中n 和m 分别为两个链表的长度。还有一点很关键啊，就是如果两个链表有一个为空，则递归结束即可。

2192 0

合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。...示例 1： c++代码：思路1：开辟一个新链表用来存放新的合并后的升序链表，每一次从l1和l2链表分别取出来一个节点，判断两个节点的值哪一个大，大的节点跟在小的节点后面，小的节点尾插到新链表后面...，并且还有判断l1和l2哪个链表长度更长，当出现一个链表遍历完后，另一个链表剩余部分就直接尾插到新链表后面 #include using namespace std; struct...ListNode* newList = new ListNode();//该链表用来存放整合后的数据 ListNode* end = newList;//指向当前链表尾节点...<< "请为l2链表赋值：" << endl; input(l2); cout << "输出l2链表: " << endl; display(l2); cout <<

1.1K3 0

算法-合并两个有序链表

https://blog.csdn.net/li_xunhuan/article/details/90142458 题目：将两个有序链表合并为一个新的有序链表并返回...新链表是通过拼接给定的两个链表的所有节点组成的。...cur.next=l2; if(l2==null) cur.next=l1; return dummyHead.next; } } 分析： 1.注意我们对于链表中的结点我们没有必要去新建一个与当前结点相同的过来...，然后对于合并结果链表进行赋值，因为这违反了结点的本质：不连续的内存单元;多创建结点无疑在空间复杂度上不优。...2.对于链表运算中加一个dummyHead可以进行把头节点作为普通结点一样来处理，不同于数组在开头多加一个元素会造成返回的数组多了一个元素，链表中结点的不连续性真的很好用 3.dummyHead的好处还在于单向链表中头节点一直都是已知的就是为

1.1K2 0

合并两个排序的链表

题目 :输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。...思想 :类似于排有序数组,,,定义新node/数组.每次遍历将小的放在node/数组中,移动小的node/数组的游标代码 package com.algorithm.offer; import com.sun.xml.internal.bind.v2...ListNode next = null; ListNode(int val) { this.val = val; } } //输入两个单调递增的链表...，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

7562 0

合并两个排序的链表

题目：输入两个递增排序的链表，合并这两个链表并使新链表中的结点仍然是按照递增排序的。例如下图中的链表1和链表2，则合并之后的升序链表如链表3所示。...注：链表1和链表2是两个递增排序的链表，合并这两个链表得到升序链表为链表3. 首先分析合并两个链表的过程。我们的分析从合并两个链表的头结点开始。...在剩余的结点中，链表2的头结点的值小于链表1的头结点的值，因此链表2的头结点是剩余结点的头结点，把这个结点和之前已经合并好的链表的尾结点链接起来。继续合并两个链表中剩余的结点（图中虚线框所示）。...在两个链表中剩下的结点依然是排序的，因此合并这两个链表的步骤和前面的步骤是一样的。我们还是比较两个头结点的值。...在本题中，当第一个链表是空链表，也就是它的头结点是一个空指针时，那么把它和第二个链表合并，显然合并的结果是第二个链表。

1K8 0

合并两个有序的链表

题目：输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。...这种链表是需要我们遍历链表的输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4 是否需要头结点：因为我们目前的头结点是不能确定的当l1.val<l=2.val...时头结点指向l1 当l1.val>l2.val 时头结点指向l2 因此我们需要一个头结点指向头结点的next 指向l1或l2 我们还需要判断边界条件两个链表不一定一样长有可能l1遍历完了...cur=cur.next; } //如果l1链表不为空 if(l1!...=null){ //如果l2链表不为空剩余的加入到cur cur.next=l2; } return dump.next

3581 0

LeetCode - 合并两个有序链表

merge-two-sorted-lists/ 题目描述：将两个有序链表合并为一个新的有序链表并返回...新链表是通过拼接给定的两个链表的所有节点组成的。...首先判断链表l1和l2是否为空，如果有一个为空，那就直接返回另一个链表即可然后就是不停的遍历链表l1和l2，分别判断两个链表当前节点的值大小，取值更小的节点，并将指向该链表的指针往后移动如果在遍历时发现某一个链表已经为空了...，那么最快的方式就是直接将链表的下一个指针指向另一个链表即可。

3675 0

合并两个排序的链表

题目描述输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

8113 0

合并两个排序的链表

前言给定两个递增排序的链表，如何将这两个链表合并？合并后的链表依然按照递增排序。本文就跟大家分享一种解决方案，欢迎各位感兴趣的开发者阅读本文。...同样的，这个问题也可以用双指针的思路来实现： p1指针指向链表1的头节点 p2指针指向链表2的头节点声明一个变量存储合并后的链表，比对两个指针指向的节点值大小：如果p1指针指向的节点值比p2指向的值小...，合并后的链表节点就取p1节点的值，p1指针继续向前走，进行下一轮的比对如果p2指针指向的节点值比p1指向的值小，合并后的链表节点就取p2节点的值，p2指针继续向前走，进行下一轮的比对当p1节点指向...null时，合并后的链表节点就为p2所指向的链表节点；当p2节点指向null时，合并后的链表节点就为p1所指向的链表节点。...MergeLinkedList(firstListHead, secondListHead.next); } return pMergedHead; } 测试用例接下来，我们用思路分析章节中的例子来测试下我们的代码能否正常执行

8261 0

leetcode链表之合并两个排序的链表

序本文主要记录一下leetcode链表之合并两个排序的链表 Sort-Linked-List.png 题目输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。 ...{ cursor.next = l1; } return newHead.next; } } 这里先创建一个newHead节点来表示合并后链表的头指针...，然后创建一个cursor，其初始值为newHead；之后同时遍历l1及l2，取最小的作为cursor.next，同时该链表前进一个节点，并且cursor跟着前进；最后再将cursor.next指向尚未遍历完的链表的剩余节点...；之后返回头指针指向的节点小结合并两个有序链表的基本思路就是设置一个cursor以及新链表的头指针，然后同时遍历两个链表，取小的节点作为cursor的next，然后该链表往前进，cursor也跟着往前进...，最后再将cursor.next指向尚未遍历完的链表的剩余节点 doc he-bing-liang-ge-pai-xu-de-lian-biao-lcof

6230 0

点击加载更多

扫码

添加站长进交流群

领取专属 10元无门槛券

手把手带您无忧上云

扫码加入开发者社群

相关资讯

热门标签

活动推荐

运营活动

活动名称

广告关闭