Leetcode: Insertion Sort List

Sort a linked list using insertion sort.

Solution:

In the previous post we already implement Insertion sort in arrays, now we deal of how to do it in single-linked lists.

We summarize the difference:

• - Traversing a single-linked in the opposite direction is very costly.
• - We can add an element in any position without having to move the next elements.

The only difficulty of this problem is to be very careful with the pointers, in order to avoid creating a loop

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode insertionSortList(ListNode head) {
        if(head==null)
            return null;
        ListNode nodeToInsert = head.next;
        while ( nodeToInsert != null)
        {
            ListNode nextToInsert = nodeToInsert.next;
            nodeToInsert.next = null;
            if(nodeToInsert.val<head.val)
            {
                nodeToInsert.next = head;
                if(head.next == nodeToInsert)
                    head.next =null;
                head = nodeToInsert;
                
            }
            else
            {
                ListNode temp = head;
                while(temp.next!=null && temp.next.val< nodeToInsert.val)
                    temp = temp.next;
                if(temp.next!=nodeToInsert)
                    nodeToInsert.next = temp.next;
                temp.next = nodeToInsert;
            }
            nodeToInsert = nextToInsert;
        }
        return head;
    }
}