Question
Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.
My idea
Compare the link node value to determine what should pointer point to.
Highlights
VALUE = node.next means VALUE point to the node's next object
node.next = VALUE means the node's next object is VALUE
My code
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
head = ListNode(0)
dummy = head
while l1 and l2:
if l1.val >= l2.val:
dummy.next = l2 #把当前节点挂到合并好的链表dummy上
l2 = l2.next #把待合并的链表的最开始节点的指针后移
else:
dummy.next = l1
l1 = l1.next
dummy = dummy.next
if l1:
dummy.next = l1
if l2:
dummy.next = l2
return head.next
Better idea
Recursion
Code
class Solution:
def mergeTwoLists(self, l1, l2):
if not l1 or not l2:
return l1 or l2
if l1.val < l2.val:
l1.next = self.mergeTwoLists(l1.next, l2)
return l1
else:
l2.next = self.mergeTwoLists(l1, l2.next)
return l2
