查看: 547|回复: 10
跳转到指定楼层
上一主题 下一主题
收起左侧

[树/链表/图] 21. Merge two sorted lists 合并有序链表这题的一个小问题

|只看干货
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (130)
 
 
0% (0)    👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
本帖最后由 熊云天 于 2021-9-9 22:30 编辑

Leetcode 第21题 Merge two sorted lists 合并有序链表,我写的是迭代解法:

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

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if not l1 or not l2:
            return l1 or l2
        l = ListNode(0)
        tmp = l.next
        while l1 and l2:
            if l1.val <= l2.val:
                tmp = l1
                l1 = l1.next
            else:
                tmp = l2
                l2 = l2.next
            tmp = tmp.next
        tmp = l1 or l2
        return l.next

但是!上述答案提交返回的结果为空list,肯定是不对的。下面的标准答案,对next指针的处理有不同,和上面答案不同的地方用粗体标注了出来:

参考的标准答案:
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if not l1 or not l2:
            return l1 or l2
        l = ListNode(0)
        tmp = l
        while l1 and l2:
            if l1.val <= l2.val:
                tmp.next = l1
                l1 = l1.next
            else:
                tmp.next = l2
                l2 = l2.next
            tmp = tmp.next
        tmp.next = l1 or l2
        return l.next

请问为什么我的写法不对呢?感觉逻辑上和标准答案没区别,就是某些地方对next指针的处理不一样。

小白刚开始刷题,希望各位不吝赐教,提前谢谢了













评分

参与人数 1大米 +5 收起 理由
14417335 + 5

查看全部评分


上一篇:刷题重复方法
下一篇:大家觉得leetcode周赛分数有真实反应自己目前的刷题/算法水平吗?
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (2153)
 
 
1% (29)    👎
你的tmp = tmp.next那行………
next了个寂寞

评分

参与人数 1大米 +1 收起 理由
熊云天 + 1 给你点个赞!

查看全部评分

回复

使用道具 举报

🔗
 楼主| 熊云天 2021-9-10 14:13:15 | 只看该作者
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (130)
 
 
0% (0)    👎
cannoli 发表于 2021-9-9 22:37
你的tmp = tmp.next那行………
next了个寂寞

没太理解... tmp = tmp.next 是标准迭代解法里面也有的啊?它的作用是当tmp节点已经赋值了l1或l2里面的当前最小值以后,走到下一个节点tmp.next继续迭代。
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (2153)
 
 
1% (29)    👎
熊云天 发表于 2021-09-09 23:13:15
没太理解... tmp = tmp.next 是标准迭代解法里面也有的啊?它的作用是当tmp节点已经赋值了l1或l2里面的当前最小值以后,走到下一个节点tmp.next继续迭代。
next是next了,和l连上了么?

评分

参与人数 2大米 +2 收起 理由
熊云天 + 1 给你点个赞!
14417335 + 1

查看全部评分

回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (52)
 
 
1% (1)    👎
你跟解答的差别在于你没有把节点连起来啊,你想像成tmp是一个一直指向当前最后一个已经接好的点,所以解答那行是tmp.next = l1 (或是tmp.next =l2) 相当于把tmp 跟下一个点接起来以后才tmp = tmp.next,相当于移动了tmp 到你接到目前为止最后的一个点,你只是tmp = l1,没有真的把节点按顺序接起来啊。你弄个简单的test case 自己跑一遍就知道了。

评分

参与人数 2大米 +4 收起 理由
熊云天 + 2 给你点个赞!
14417335 + 2

查看全部评分

回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   99% (233)
 
 
0% (1)    👎
因为你认为的tmp=l.next和它实际的不一样。l.next是None. 所以最开始tmp在第一次赋值后就是None。随后你又赋值tmp为l1或者l2,这样相当于第一次赋值语句不起作用,而且tmp=l1不代表l.next也等于l1了,因为tmp和l.next仅仅是值一样。

很简单的例子:
a=2
b=a
b+=1
此时你会认为a=3吗

补充内容 (2021-09-10 23:43 +08:00):
https://zhuanlan.zhihu.com/p/331732504

评分

参与人数 1大米 +2 收起 理由
熊云天 + 2 给你点个赞!

查看全部评分

回复

使用道具 举报

🔗
AituiNTI 2021-9-11 00:39:30 | 只看该作者
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   93% (139)
 
 
6% (10)    👎
lz需要知道的是,tmp.next = l1,当temp.next在等号左边的时候,代表的是把temp的节点的指针指向l1,这是一个动作;所以你首先要搞清楚temp.next在等号左右两边时有啥区别

评分

参与人数 1大米 +2 收起 理由
熊云天 + 2 给你点个赞!

查看全部评分

回复

使用道具 举报

🔗
 楼主| 熊云天 2021-9-11 02:38:55 | 只看该作者
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (130)
 
 
0% (0)    👎
cannoli 发表于 2021-9-9 23:35
next是next了,和l连上了么?

我理解的是在code最开始 tmp = l.next,应该是l的下一个节点指向了tmp。最后一步return l.next,应该能串联出整个tmp和tmp链接的节点。~~
回复

使用道具 举报

🔗
 楼主| 熊云天 2021-9-11 03:11:46 | 只看该作者
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (130)
 
 
0% (0)    👎
JudyTsai 发表于 2021-9-9 23:55
你跟解答的差别在于你没有把节点连起来啊,你想像成tmp是一个一直指向当前最后一个已经接好的点,所以解答 ...

好像有点懂了,tmp.next = l1 (或者l2) 这句和tmp = tmp.next一起才能把tmp中的节点链接起来。如果是tmp = l1, tmp = tmp.next好像没真正连起来!
回复

使用道具 举报

🔗
 楼主| 熊云天 2021-9-11 03:16:16 | 只看该作者
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (130)
 
 
0% (0)    👎
T大农民伯伯 发表于 2021-9-10 08:27
因为你认为的tmp=l.next和它实际的不一样。l.next是None. 所以最开始tmp在第一次赋值后就是None。随后你又 ...

就是tmp = l.next相当于tmp = None。tmp再赋值l1(或l2)没有和l进行有效的链接。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表