Golang in-place merge sort, 19ms


  • 0
    C

    Although kind of ugly

    func helper(lists []*ListNode, start, end int) *ListNode {
        if start == end {
            return lists[start]
        }
        mid := (start+end)/2
        a := helper(lists, start, mid)
        b := helper(lists, mid+1, end)
        return merge(a, b)
    }
     
    func merge(list1, list2 *ListNode) *ListNode {
        if list1 == nil || list2 == nil {
            if list1 == nil {
                return list2
            } else {
                return list1
            }
        }
        
        var head *ListNode
        if list1.Val < list2.Val {
            head = list1
            list1 = list1.Next
        } else {
            head = list2
            list2 = list2.Next
        }
        pCur := head
        for list1 != nil && list2 != nil {
            if list1.Val < list2.Val {
                pCur.Next = list1
                list1 = list1.Next
            } else {
                pCur.Next = list2
                list2 = list2.Next
            }
            pCur = pCur.Next
        }
        if list1 == nil {
            pCur.Next = list2
        } else {
            pCur.Next = list1
        }
        
        return head
    }
     
    func mergeKLists(lists []*ListNode) *ListNode {
        if len(lists) == 0 || lists == nil {
            return nil
        }
        return helper(lists, 0, len(lists)-1)
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.