【Leetcode】【python】Merge Two Sorted Lists 合并两个有序链表

题目大意

合并两个排好序的链表

解题思路

已开始将其当成两个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

总结

1. 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 即新的链表。

3. 链表总结
   参考：http://ryanleetcode.blogspot.com/2015/06/blog-post.html