sort-list.go

// https://leetcode.com/problems/sort-list

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func sortList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    
    middle := splitList(head)
    
    return merge(sortList(head), sortList(middle))
}

func splitList(head *ListNode) *ListNode {
    var prev *ListNode
    hare := head
    tortoise := head
    
    for hare != nil && hare.Next != nil {
        hare = hare.Next.Next
        prev = tortoise
        tortoise = tortoise.Next
    }
    
    prev.Next = nil
    
    return tortoise
}

func merge(a, b *ListNode) (result *ListNode) {
    if a == nil {
        return b
    }
    
    if b == nil {
        return a
    }
    
    if a.Val < b.Val {
        a.Next = merge(a.Next, b)
        result = a
    } else {
        b.Next = merge(a, b.Next)
        result = b
    }
    
    return
}