+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2019-08(95)

2019-09(92)

2019-10(7)

2019-11(7)

2019-12(17)

LeetCode-21 Merge Two Sorted Lists

发布于2020-03-26 11:08     阅读(750)     评论(0)     点赞(28)     收藏(1)


Description

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

Submissions

起初我对链表与列表有点混淆,所以解题思路是当l1和l2都不为空时,判断当前节点位置的值,从小到大依次添加到定义的列表out中。当l1或l2为空时,便直接将剩余的非空链表的值添加到out中。得到排好序的列表后,再定义一条链表,把它们依次存入,最后返回链表。

实现代码如下:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if l1 is None:
            return l2
        if l2 is None:
            return l1
        if l1 is None and l2 is None:
            return None
        
        out = []
        while l1 and l2:
            if l1.val <= l2.val:
                out.append(l1.val)
                l1 = l1.next
            else:
                out.append(l2.val)
                l2 = l2.next
        if l1 is None :
            while l2:
                out.append(l2.val)
                l2 = l2.next
        else:
            while l1:
                out.append(l1.val)
                l1 = l1.next
        
        pre = ListNode(-1)
        l3 = pre
        for i in range(len(out)):
            l3.next=ListNode(out[i])
            l3 = l3.next
        
        return pre.next

Runtime: 40 ms
Memory Usage: 12.9 MB

经过调整,我的解题思路是利用迭代法,首先定义pre和l3开始于同一个结点,l3会不断后移,pre负责保留头结点索引。然后进入循环,当两个链表都不为空时,判断l1和l2当前位置的值,如果 l1 当前位置的值小于等于 l2 ,就把 l1 的值接在 l3 节点的后面同时将 l1 指针往后移一个,否则把 l2的值接在 l3 节点的后面同时将 l2 指针往后移一个。同时我们都要把l3向后移一个元素。当 l1或l2为空时,就简单把剩余的非空链表与l3合并,最后返回合并链表。

实现代码如下:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:        
        pre = ListNode(-1)
        l3 = pre
        while l1 and l2:
            if l1.val <= l2.val:
                l3.next = l1
                l1 = l1.next
            else:
                l3.next = l2
                l2 = l2.next
            l3 = l3.next
        
        l3.next = l1 if l1 is not None else l2
        
        return pre.next

Runtime: 36 ms
Memory Usage: 12.9 MB

原文链接:https://blog.csdn.net/weixin_41875619/article/details/105093607



所属网站分类: 技术文章 > 博客

作者:ryuer8423

链接: https://www.pythonheidong.com/blog/article/285033/

来源: python黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

28 0
收藏该文
已收藏

评论内容:(最多支持255个字符)