[Leetcode][python]Merge Two Sorted Lists/合并两个有序链表
[Leetcode][python]Merge Two Sorted Lists/合并两个有序链表
蛮三刀酱
发布于 2019-03-26 16:45:13
发布于 2019-03-26 16:45:13
题目大意
合并两个排好序的链表
解题思路
已开始将其当成两个list，去分别修改其值，但其实应该修改的是链表的指针。 并且还有一个值得注意的是dummy node，见总结。
代码
class Solution(object):
def mergeTwoLists(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
dummy = ListNode(0)
curr = dummy
while l1 and l2:
if l1.val < l2.val:
curr.next = l1
l1 = l1.next
else:
curr.next = l2
l2 = l2.next
curr = curr.next
curr.next = l1 or l2 # 剩余的一个队列之后的全加上
return dummy.next总结
- Dummy Node Dummy node 是一个虚拟节点，也可以认为是标杆节点。Dummy node 就是在链表表头 head 前加一个节点指向 head，即 dummy -> head。Dummy node 的使用多针对单链表没有前向指针的问题，保证链表的 head 不会在删除操作中丢失。除此之外，还有一种用法比较少见，就是使用 dummy node 来进行head的删除操作，比如 Remove Duplicates From Sorted List II，一般的方法current = current.next 是无法删除 head 元素的，所以这个时候如果有一个dummy node在head的前面。 所以，当链表的 head 有可能变化（被修改或者被删除）时，使用 dummy node 可以很好的简化代码，最终返回 dummy.next 即新的链表。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017年08月22日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录