LeetCode - Insertion Sort List

Question Definition

Sort a linked list using insertion sort.

Java Solution

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

Comments