Sort a linked list using insertion sort - The Coding Shala

Home >> Interview Questions >> sort a linked list using insertion sort

 In this post, we will learn how to sort a linked list using insertion sort and will implement a Java solution.

Sort a linked list using insertion sort in Java

Sort a linked list using insertion sort.

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

Java Program:

/**
 * 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 dummy = new ListNode(0);
        ListNode curr = head, prevNode, nextNode;
        while(curr != null) {
            //set the prevNode and nextNode at starting of sorted list
            prevNode = dummy;
            nextNode = prevNode.next;
            
            //loop through sorted list
            while(nextNode != null) {
                //insert position
                if(curr.val < nextNode.val) break;
                
                prevNode = nextNode;
                nextNode = nextNode.next;
            }
            
            //insert into the sorted list
            ListNode tmp = curr.next;
            //insert key in sorted list
            prevNode.next = curr;
            curr.next = nextNode;
            //move current list
            curr = tmp;
        }
        return dummy.next;
    }
}

Other Posts You May Like

• Detect cycle in a linked list
• Reverse a linked list
• Copy a linked list with a random pointer
• Rotate a linked list
• Flatten a multilevel doubly linked list

Please leave a comment below if you like this post or found some error, it will help me to improve my content.