### 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

## Comments

## Post a Comment