Discussion on: LeetCode "Merge Two Sorted Lists"

View post

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

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

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