排序链表

1. 题目描述

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

2. 思路

参考排序.md

1. 思路一
   • 选择排序
   • 固定一个节点，从后面的节点中选择一个最小的与之交换
2. 思路二
   • 先转换成数组然后排序
   • 转换回链表
3. 思路三
   • 归并排序
4. 思路四
   1. 快速排序

3. 实现

3.1. 选择排序

func sortList(head *ListNode) *ListNode {
	//选择排序
	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. 数组排序

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. 归并排序

/**
 * 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需要初始化为head.Next
    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. 快速排序

/**
 * 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. 参考

• Sort List （归并排序链表） - 排序链表 - 力扣（LeetCode）