147. 对链表进行插入排序

对链表进行插入排序。

Insertion-sort-example-300px.gif

<small style="box-sizing: border-box; font-size: 12px;">插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。
每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。</small>

插入排序算法：

1. 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
2. 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
3. 重复直到所有输入数据插入完为止。

示例 1：

输入: 4->2->1->3
输出: 1->2->3->4
示例 2：

输入: -1->5->3->4->0
输出: -1->0->3->4->5

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func insertionSortList(head *ListNode) *ListNode {
    newNode := head

    arrayList := make([]*ListNode, 0)
    arrayList = append(arrayList, head)
    for {
        head = head.Next
        if head == nil {
            break
        }
        arrayList = append(arrayList, head)
    }
    for i := 1; i <= len(arrayList)-1; i++ {
        j := i
        z := i - 1
        for {
            if z < 0 {
                break
            }
            if arrayList[j].Val <= arrayList[z].Val {
                temp := arrayList[j]
                arrayList[j] = arrayList[z]
                arrayList[z] = temp
                j--
                z--
            } else {
                break
            }

        }
    }
    for i := 0; i <= len(arrayList)-1; i++ {
        newNode.Next = arrayList[i]
        newNode = newNode.Next
    }
    return newNode.Next
}


func insertionSortList(head *ListNode) *ListNode {
    begin := head
    end := head
    current := begin.Next
    if end == nil {
        return head
    }

    for {
        if end == nil {
            break
        }
        if current == nil {
            break
        }
        if current.Val >= end.Val {
            end.Next = current
            end = current
            current = current.Next
        } else {
            before := begin
            from := begin
            for {
                if current.Val < from.Val {
                    now := current.Next
                    current.Next = from
                    if before != from {
                        before.Next = current
                    } else {
                        begin = current
                    }
                    current = now
                    break
                }

                if current.Val > from.Val && from != end {
                    before = from
                    from = from.Next
                }
            }
        }

    }
    return begin
}