題目要求：
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.
歸并兩個(gè)已經(jīng)排序好的鏈表，歸并好了仍然是有序鏈表。
Example:
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4
巧用頭指針
# Time: O(n)
# Space: O(1)
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def mergeTwoLists(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
new_head = ListNode(0) #兩個(gè)指針指向頭節(jié)點(diǎn)
head = new_head #兩個(gè)指針指向頭節(jié)點(diǎn)
while l1 and l2:
if l1.val > l2.val:
new_head.next = l2
l2 = l2.next
else:
new_head.next = l1
l1 = l1.next
new_head = new_head.next #這一步很重要，自己的習(xí)慣是寫(xiě)進(jìn)上面的if趟卸、else里面
if l1:
new_head.next = l1
elif l2:
new_head.next = l2
return head.next
# Time: O(n)
# Space: O(1)
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def mergeTwoLists(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
curr = dummy = ListNode(0) #兩個(gè)指針指向頭節(jié)點(diǎn)贮庞，命名更易區(qū)分
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 #對(duì)于if峦筒、else而言都需要的操作可以提取出來(lái)
curr.next = l1 or l2 #python的or操作，那個(gè)為真執(zhí)行哪個(gè)
return dummy.next
