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; = 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 =;
            //loop through sorted list
            while(nextNode != null) {
                //insert position
                if(curr.val < nextNode.val) break;
                prevNode = nextNode;
                nextNode =;
            //insert into the sorted list
            ListNode tmp =;
            //insert key in sorted list
   = curr;
   = nextNode;
            //move current list
            curr = tmp;

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


Popular Posts from this Blog

Shell Script to find sum, product and average of given numbers - The Coding Shala

Shell Script to Create a Simple Calculator - The Coding Shala

Add two numbers in Scala - The Coding Shala

New Year Chaos Solution - The Coding Shala

Richest Customer Wealth LeetCode Solution - The Coding Shala