<归并排序思想>
<递归不好想啊>
<虚拟头结点技巧>
题目
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
我的思路
(错误)
1.先找到表头值最小的链表
2.遍历这个链表L1，对于node1，在L2中有 node1.val <= node2.val <= node1.next.val ，把这个node2插入到node1和node1.next之间
这种在原链表上进行裁缝操作很麻烦，易出错。一部小心就破坏了列表。
题解 - 迭代
详见官方题解
class Solution: def mergeTwoLists(self, l1, l2): # maintain an unchanging reference to node ahead of the return node. prehead = ListNode(-1) prev = prehead while l1 and l2: if l1.val <= l2.val: prev.next = l1 l1 = l1.next else: prev.next = l2 l2 = l2.next prev = prev.next # exactly one of l1 and l2 can be non-null at this point, so connect # the non-null list to the end of the merged list. prev.next = l1 if l1 is not None else l2 return prehead.next 作者：LeetCode 链接：https://leetcode-cn.com/problems/two-sum/solution/he-bing-liang-ge-you-xu-lian-biao-by-leetcode/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
总结
1.链表遍历的两种方式
while node: pass node = node.next print(node) # node=None while not node.next is None: pass node = node.next print(node) # node=最后一个节点
2.新增一个带表头的空链表
prehead = ListNode(-1)
根据模板的注释得知ListNode是用来构造链表的类，这个类实例化的时候有带参数，所以是ListNode(-1)，括号里可以为其他值。
因为构造了一个表头值为-1的空链表，所以最后返回结果的时候是 return pre.next