LeetCode - Insertion Sort List

Question Definition

Sort a linked list using insertion sort.

Java Solution

public ListNode insertionSortList(ListNode head) {
    if(head == null) return head;
    ListNode newHead = new ListNode(head.val);
    head = head.next;
    while(head != null){
        ListNode node = new ListNode(head.val);
        if(head.val <= newHead.val){
            node.next = newHead;
            newHead = node;
            head = head.next;
            continue;
        }

        ListNode pre = newHead;
        while(pre.next != null && pre.next.val < head.val)
            pre = pre.next;
        if(pre.next == null){
            pre.next = node;
        }else{
            node.next = pre.next;
            pre.next = node;
        }
        head = head.next;
    }
    return newHead;
}

Comments