DEV Community

Takahiro Kudo
Takahiro Kudo

Posted on

LeetCode "Merge Two Sorted Lists"

Recursive, Recursive, Recursive...🤮

Reference
https://leetcode.com/problems/merge-two-sorted-lists/discuss/381943/python-concise-recursion-code

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
Enter fullscreen mode Exit fullscreen mode

Top comments (3)

Collapse
 
theodesp profile image
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
}
Collapse
 
takakd profile image
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
Collapse
 
takakd profile image
Takahiro Kudo

Oh! Thanks!
I'll try in python🙇🏻‍♂️