Takahiro Kudo

Posted on

# LeetCode "Merge Two Sorted Lists"

Recursive, Recursive, Recursive...๐คฎ

``````class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if l1 is None and l2 is None:
return None
elif l1 is None:
return l2
elif l2 is None:
return l1

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

## Top comments (3)

Theofanis Despoudis

You can also do it iteratively. This is the merge part of the merge sort algorithm:

``````func Merge(left []int, right []int) []int {
result := make([]int, len(left)+len(right))

i := 0
for len(left) > 0 && len(right) > 0 {
if left[0] < right[0] {
result[i] = left[0]
left = left[1:]
} else {
result[i] = right[0]
right = right[1:]
}
i++
}

for j := 0; j < len(left); j++ {
result[i] = left[j]
i++
}
for j := 0; j < len(right); j++ {
result[i] = right[j]
i++
}

return result
}
``````

Takahiro Kudo

Great help. Thank you! โบ๏ธ

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

first = ListNode(-1)
ret = first
l1_node = l1
l2_node = l2

while l1_node or l2_node:
if not l1_node:
ret.next = l2_node
break
elif not l2_node:
ret.next = l1_node
break

if l1_node.val <= l2_node.val:
tmp = l1_node.next
ret.next = l1_node
l1_node = tmp
else:
tmp = l2_node.next
ret.next = l2_node
l2_node = tmp
ret = ret.next
ret.next = None

return first.next
``````

Takahiro Kudo

Oh! Thanks!
I'll try in python๐๐ปโโ๏ธ