sort_linked_list.go

/*
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
*/

func sortList(list *ListNode) *ListNode {
	if list == nil || list.Next == nil {
		return list
	}

	left, right := split(list)
	left = sortList(left)
	right = sortList(right)
	return merge(left, right)
}

func merge(a, b *ListNode) *ListNode {
	if a == nil {
		return b
	}

	if b == nil {
		return a
	}

	var head, tail *ListNode
	for a != nil && b != nil {
		if a.Val <= b.Val {
			if head == nil {
				head = a
				tail = a
			} else {
				tail.Next = a
				tail = tail.Next
			}
			a = a.Next
		} else {
			if head == nil {
				head = b
				tail = b
			} else {
				tail.Next = b
				tail = tail.Next
			}
			b = b.Next
		}
	}

	if a != nil {
		tail.Next = a
	}

	if b != nil {
		tail.Next = b
	}

	return head
}

func split(list *ListNode) (*ListNode, *ListNode) {
	slow, fast := list, list.Next

	for fast != nil {
		fast = fast.Next
		if fast != nil {
			slow = slow.Next
			fast = fast.Next
		}
	}

	slow, slow.Next = slow.Next, nil
	return list, slow
}