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

```/**
* 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 {
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