LeetCode - Insertion Sort List

Problem description

description

Sort a linked list using insertion sort.

Algorithm of Insertion Sort:

1. Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list.
2. At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there.
3. It repeats until no input elements remain.

Example 1:

Input: 4->2->1->3
Output: 1->2->3->4

Example 2:

Input: -1->5->3->4->0
Output: -1->0->3->4->5

Analysis

Just write the code:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode sorted = new ListNode(0);
        
        while(head != null){
            ListNode next = head.next;

            ListNode p = sorted;
            
            while(p.next != null && p.next.val < head.val){
                p = p.next;
            }
            
            head.next = p.next;
            p.next = head;
            
            head = next;
        }
        
        return sorted.next;
    }
}

An improvement:

class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode dummy = new ListNode(0);
        ListNode prev = dummy;

        while (head != null) {
            ListNode temp = head.next;
            
            /* Before insert, the prev is at the last node of the sorted list.
            Only the last node's value is larger than the current inserting node 
            should we move the temp back to the head*/
            if (prev.val >= head.val) prev = dummy;

            while (prev.next != null && prev.next.val < head.val) {
                prev = prev.next;
            }
            
            head.next = prev.next;
            prev.next = head;
            // prev = dummy; // Don't set prev to the head of the list after insert
            head = temp;
        }
        return dummy.next;
    }
}

What to improve

• we can check if last node is bigger than cur then make it be the head of the sorted list.