LeetCode "Merge Two Sorted Lists"

#leetcode #python

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

Top comments (3)

Theofanis Despoudis • Oct 22 '19

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 • Nov 2 '19

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 • Oct 23 '19

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

DEV Community

LeetCode "Merge Two Sorted Lists"

Top comments (3)

Read next

Gemini API 102: Next steps beyond "Hello World!"

What Will You Choose?

LeetCode

Start with Python Dictionaries