Sort List Leetcode


#1

Sort a linked list in O(n log n) time using constant space complexity.

Example 1:

Input: 4->2->1->3
Output: 1->2->3->4

Example 2:

Input: -1->5->3->4->0
Output: -1->0->3->4->5

#2

Uses merge sort style logic to divide the nodes and merge them.

/**
 * 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
    }
    
    var prev *ListNode
    slow, fast := head, head
   
    for fast!=nil && fast.Next!=nil{
        fast = fast.Next.Next
        prev = slow
        slow = slow.Next
    }
    
    // break the list into half
    prev.Next = nil
    
    l1  := sortList(head)
    l2 := sortList(slow)
    
    return merge(l1, l2)
}

func merge(l1 *ListNode ,l2 *ListNode ) *ListNode {
    temp := new(ListNode)
    tempHead := temp
    for l1!=nil && l2!=nil{
        if l1.Val < l2.Val{
            temp.Next = l1
            l1 = l1.Next
        } else {
             temp.Next = l2
             l2 = l2.Next
        }
        temp = temp.Next
    }
    
    if l1!=nil{
         temp.Next = l1
    }
    
    if l2!=nil{
         temp.Next = l2
    }
    
    return tempHead.Next
}