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