以前C 就看链表头疼，干脆做个图示， 作为链表题的开始。
题目来了：
https://leetcode.com/problems/merge-two-sorted-lists/
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.
要点：
- 链表是有序的已经
朴素（我的）解法：
代码语言：javascript复制# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def mergeTwoLists(self, list1, list2):
"""
:type list1: Optional[ListNode]
:type list2: Optional[ListNode]
:rtype: Optional[ListNode]
"""
if list1 is None:
return list2
if list2 is None:
return list1
head = ListNode(0)
cur = head
while list1 and list2:
if list1.val < list2.val:
cur.next = list1
list1 = list1.next
else:
cur.next = list2
list2 = list2.next
cur = cur.next
cur.next = list1 or list2
return head.next借用例子1：
代码语言：javascript复制Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]来做个图解， 图解的点子来自 https://blog.csdn.net/Varalpha/article/details/104997416， 我做个这个题对应更详细的
如果list1 或 list2 是空的， 就返回另一个就行了。
从开始 head = {val:0, next:None} 不指向任何ListNode。
然后 cur = head = {val:0, next:None} 开始遍历list1 和list2, 其中一个的遍历完后结束。
第一次：
对比 list1 = {val:1, next : {val:2,next: {val:4, next:None}}} 和 list2 = {val:1, next : {val:3,next: {val:4, next:None}}}
这里接入list2, 就是 cur = head = {val:0, next: list2 = {1, next: {...}}} 把， cur本来指向的None换成了list2的第一个Node
然后 list2 = list2.next = {val:3,next: {val:4, next:None}}, 就是list2现在从原本list2.next开始，
每次不管list1或List2接入cur.next之后， list1或list2更新， 然后cur = cur.next = {val:1, next: {...}}, 现在cur从原本cur.next的位置开始。 这里其实是指向list2后半部分了， 就是next接上了 【3，4】, 但是之后的遍历中，next的指向根据val会变
第二次：。。。。。
最后多出来的List1 或list2 整个接到next后面去
然后因为最早第一次的时候cur接到了cur.next也就是head.next后面， 那么返回head.next就可以得到之后多次改变指向的cur。
官方给出的递归的方法是：
代码语言：javascript复制# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def mergeTwoLists(self, list1, list2):
"""
:type list1: Optional[ListNode]
:type list2: Optional[ListNode]
:rtype: Optional[ListNode]
"""
if list1 is None:
return list2
elif list2 is None:
return list1
elif list1.val < list2.val:
list1.next = self.mergeTwoLists(list1.next,list2)
return list1
else:
list2.next = self.mergeTwoLists(list2.next,list1)
return list2 根据第一个Node哪个list.val小来决定从哪儿开始，简洁，牛的
