LeetCode #21 2018-07-28

21. Merge Two Sorted Lists

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

https://leetcode.com/problems/merge-two-sorted-lists/description/

一般来说合并的思路就是以一个为主参考，然后逐项比较，如果较小元素在参考链表中，则继续前进，否则把结点插入参考链表中，前进另一个链表， 最后如果另一个链表还没到头就直接接过来就可以了。维护两个指针对应两个链表，因为一般会以一条链表为基准，比如说l1, 那么如果l1当前那的元素比较小，那么直接移动l1即可，否则将l2当前的元素插入到l1当前元素的前面。算法时间复杂度是O(m+n),m和n分别是两条链表的长度，空间复杂度是O(1).
dummy是一种链表比较常见的技巧，就是在链表头构造一个空节点，这样是有利于链表操作中需要改动链表头时不需要分情况讨论。
代码如下：

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

class Solution:
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        dummy = ListNode(0)
        dummy.next = l1
        pre = dummy
        while(l1 and l2):
            if l1.val <= l2.val:
                l1 = l1.next
            else:
                next = l2.next
                l2.next = pre.next
                pre.next = l2
                l2 = next
            pre = pre.next
        if l2:
            pre.next = l2
        return dummy.next

感悟:

1. 在我们需要改变链表头部的时候，我们可以创建一个虚拟结点在头部前面，这样可以避免讨论，而且最后返回dummy.next即为新链表的头部，非常方便。
2. pre结点开始指向dummy，当l1指向空时，pre正好指向最后一个结点。所以如果l2还没空，直接把l2接到pre后面即可。
3. 这种以1个链表为参照的方法思想非常好，值得借鉴。