LeetCode147. 对链表进行插入排序-Java&Go-头插法

• 算法
  • 1.头插法
  • 2.插入前先记录下一个要插入的节点，然后从头开始找插入位置

public ListNode insertionSortList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }

    ListNode dummy = new ListNode(Integer.MIN_VALUE);
    ListNode insertNode = head;
    while (insertNode != null) {
        ListNode insertNext = insertNode.next;
        ListNode prev = dummy;
        while (prev.next != null && prev.next.val <= insertNode.val) {
            prev = prev.next;
        }
        insertNode.next = prev.next;
        prev.next = insertNode;
        insertNode = insertNext;
    }
    return dummy.next;
}

func insertionSortList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }

    dummy := &ListNode{}
    insertNode := head
    for insertNode != nil {
        insertNext := insertNode.Next
        prev := dummy
        for prev.Next != nil && prev.Next.Val <= insertNode.Val {
            prev = prev.Next
        }
        insertNode.Next = prev.Next
        prev.Next = insertNode
        insertNode = insertNext
    }
    return dummy.Next
}