leetcode21-- Merget 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



class Solution(object):
def mergeTwoLists(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""

if not l1:
return l2
if not l2:
return l1

if l1.val > l2.val:
l1, l2 = l2, l1

l1.next = self.mergeTwoLists(l1.next, l2)

return l1




class Solution(object):
def mergeTwoLists(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""

if not l1:
return l2
if not l2:
return l1

ret = ListNode(min(l1.val, l2.val))

if l1.val < l2.val:
ret.next = self.mergeTwoLists(l1.next, l2)
else:
ret.next = self.mergeTwoLists(l1, l2.next)

return ret



class Solution(object):
def mergeTwoLists(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""

ret2 = ListNode(-1)
ret = ret2

while (l1 and l2):
if (l1.val<l2.val):
ret.next = l1
l1 = l1.next
else:
ret.next = l2
l2 = l2.next

ret = ret.next
if l1:
ret.next=l1
else:
ret.next=l2

return ret2.next



ret2是这个最终要返回的head,然后让ret不断地往下加长，因为最初是加了个-1的，所以最终应该返回ret2.next.


# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:

ret = ListNode(-1)
root = ret

while l1 and l2:
if l1.val<=l2.val:
root.next = ListNode(l1.val)   # 这里和上面写的不太一样.
l1 = l1.next
else:
root.next = ListNode(l2.val)
l2 = l2.next

root = root.next

if l1:
root.next = l1
if l2:
root.next = l2

return ret.next