DEV Community

loading...

LeetCode "Merge Two Sorted Lists"

takakd profile image Takahiro Kudo ・1 min read

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

Discussion

pic
Editor guide
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 Author

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 Author

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