ノードの選択ソート
https://gyazo.com/3925fd1b0862d8afbb6b6c23a8338064
上記のような単方向リストをソートする問題
code:sort.go
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func insertionSortList(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
// ソート済みノードが入っていく
dummy := &ListNode{}
for cur := head; cur != nil; {
nextNode := cur.Next
// ソート済みノードのうち、curを格納すべき最新ノード
pos := dummy
for pos.Next != nil && pos.Next.Val < cur.Val {
pos = pos.Next
}
cur.Next = pos.Next
pos.Next = cur
cur = nextNode
}
return dummy.Next
}