Sort List

1. Problem Description

Given the head head of a linked list, sort the list in ascending order and return the sorted list.

Follow-up: Can you sort the linked list in O(n log n) time and constant extra space?

2. Approach

See Sorting

1. Approach 1
   • Selection sort
   • Fix one node, then find the smallest node among the remaining nodes and swap their values
2. Approach 2
   • Convert the linked list to an array and sort it
   • Convert it back to a linked list
3. Approach 3
   • Merge sort
4. Approach 4
   1. Quicksort

3. Implementation

3.1. Selection Sort

func sortList(head *ListNode) *ListNode {
	// Selection sort
	current := head
	for current != nil {
		minNode := current
		next := current.Next
		for next != nil {
			if next.Val < minNode.Val {
				minNode = next
			}
			next = next.Next
		}
		current.Val, minNode.Val = minNode.Val, current.Val
		current = current.Next
	}

	return head
}

3.2. Array Sort

func sortList2(head *ListNode) *ListNode {
	current := head
	ints := make([]int, 0)
	for current != nil {
		ints = append(ints, current.Val)
		current = current.Next
	}
	sort.Ints(ints)

	current = head
	for i := 0; i < len(ints); i++ {
		current.Val = ints[i]
		current = current.Next
	}

	return head
}

3.3. Merge Sort

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

    // fast must be initialized to head.Next here
    fast := head.Next
    slow := head
    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
    }

    mid := slow.Next
    slow.Next = nil
    left := sortList(head)
    right := sortList(mid)

    return merge2List(left, right)
}

func merge2List(left, right *ListNode) *ListNode {
    dummyHead := &ListNode{}
    d := dummyHead
    for left != nil && right != nil {
        if left.Val < right.Val {
            d.Next = left
            left = left.Next
        }else {
            d.Next = right
            right = right.Next
        }
        d = d.Next
    }
    if left != nil {
        d.Next = left
    }
    if right != nil {
        d.Next = right
    }
    return dummyHead.Next
}

3.4. Quicksort

/**
 * 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
	}
	left,mid,right := partition(head)
	left = sortList(left)
	right = sortList(right)
	
    return merge2List(merge2List(left, mid), right)
}

func merge2List(left, right *ListNode) *ListNode {
    if left == nil {return right}
    if right == nil {return left}
    current := left
    for current.Next != nil {
        current = current.Next
    }
    current.Next = right
    return left
}

func partition(head *ListNode) (*ListNode, *ListNode, *ListNode) {
	if head == nil  {
		return nil, nil, nil
	}
	pivot := head
	leftDummyHead := &ListNode{}
	rightDummyHead := &ListNode{}
    midDummyHead := &ListNode{}
	l := leftDummyHead
	r := rightDummyHead
    m := midDummyHead
	current := head
	for current != nil {
		next := current.Next
        current.Next = nil
		if current.Val < pivot.Val {
			l.Next = current
			l = l.Next
		} else if current.Val > pivot.Val{
			r.Next = current
			r = r.Next
		} else {
            m.Next = current
            m = m.Next
        }
		current = next
	}
	return leftDummyHead.Next, midDummyHead.Next, rightDummyHead.Next
}

4. References

• Sort List (Merge Sort for Linked Lists) - LeetCode