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

LeetCode - Crawler Log Folder Solution - The Coding Shala

Richest Customer Wealth LeetCode Solution - The Coding Shala

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

First Unique Character in a String Java - The Coding Shala

Add two numbers in Scala - The Coding Shala