【LintCode 简单】165. 合并两个排序链表

小灰灰 2022-06-01 04:08 162阅读 0赞

1.问题描述：

将两个排序链表合并为一个新的排序链表。

2.样例:

给出 `1->3->8->11->15->null`，`2->null`， 返回 `1->2->3->8->11->15->null`。

3.代码：

"""
    Definition of ListNode
    class ListNode(object):
        def __init__(self, val, next=None):
            self.val = val
            self.next = next
    """
    
    
    class Solution:
        """
        @param: l1: ListNode l1 is the head of the linked list
        @param: l2: ListNode l2 is the head of the linked list
        @return: ListNode head of linked list
        """
        def mergeTwoLists(self, l1, l2):
            # write your code here
            if l1 is None:
                return l2
            elif l2 is None:
                return l1
            else:
                if l1.val <= l2.val:
                    newhead=p=l1
                    l1=l1.next
                else:
                    newhead=p=l2
                    l2=l2.next
                    
                while l1 and l2: 
                    if l1.val <= l2.val:
                        p.next=l1
                        l1=l1.next
                        p=p.next
                    else:
                        p.next=l2
                        l2=l2.next
                        p=p.next
                if l1:
                    p.next=l1
                if l2:
                    p.next=l2
            return newhead

本题思路并不复杂，代码看起来稍有点多。主要分为几种情况：

1）l1或l2中如果有None，则直接返回另外一个链表即可

2）需要判断两个链表的头结点的大小，确定新链表的头结点

3）当某个链表的数已经全部加到新链表中后，把另外一个链表剩余的数加入即可

发表评论取消回复

表情：

评论列表（有 0 条评论，162人围观）

还没有评论，来说两句吧...

相关阅读

相关合并两个排序的链表

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

Dear 丶/ 2024年02月19日 13:38/ 0 赞/ 40 阅读

相关合并两个排序的链表

时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M 热度指数：899289 题目描述输入两个单调递增的链表，输出两个链表合成后的

蔚落/ 2023年01月13日 09:49/ 0 赞/ 210 阅读

相关合并两个排序的链表

class Solution { / 递归的方式依次比较 / public ListNode mergeTwoLists(ListN

朴灿烈づ我的快乐病毒、/ 2022年10月30日 05:22/ 0 赞/ 159 阅读

相关【链表】合并两个排序的链表

First \------ 递归思路，需要重新创建一个链表，空间复杂度O(1) ListNode Merge(ListNode pHead1, ListNode p

绝地灬酷狼/ 2022年09月25日 11:28/ 0 赞/ 173 阅读

相关算法-合并两个排序的链表

题目：输入两个递增排序的链表，合并着两个链表并使新链表中的结点仍然是按照递增顺序的。例如输入的链表1和链表2如下，合并后的为链表3。链表的结点定义如下： str

一时失言乱红尘/ 2022年06月11日 08:45/ 0 赞/ 201 阅读

相关合并两个排序的链表

题目描述输入两个单调递增的链表，输出两个链表合并后的链表，当然我们需要合并后的链表满足单调不减规则。方法一，非递归，循环比较两个节点的大小 / pub

叁歲伎倆/ 2022年06月08日 01:11/ 0 赞/ 178 阅读

相关【LintCode 简单】165. 合并两个排序链表

1.问题描述：将两个排序链表合并为一个新的排序链表。 2.样例: 给出 `1->3->8->11->15->null`，`2->null`，返回 `1->2->

小灰灰/ 2022年06月01日 04:08/ 0 赞/ 163 阅读

相关合并两个排序的链表

![这里写图片描述][70] class ListNode { int val; ListNode next = null;

绝地灬酷狼/ 2022年05月26日 13:36/ 0 赞/ 168 阅读

相关链表问题_合并两个排序链表

题目：输入两个递增排序的链表，合并这两个排序链表，使得合并之后的链表仍然使递增排序的。分析：即是归并排序中的归并操作，有两种具体的实现：1、使用递归的方法，2、迭代版本，

╰+哭是因爲堅強的太久メ/ 2022年05月21日 01:57/ 0 赞/ 192 阅读

相关合并两个排序的链表

时间限制：1秒空间限制：32768K 热度指数：390585 本题知识点：链表算法知识视频讲解题目描述输入两个单调递增的链表，输出两个链表合成后的链表

深碍√TFBOYSˉ_/ 2022年03月10日 01:37/ 0 赞/ 201 阅读