Insertion Sort Linked List Editorial

Practice Problem Link: Insertion Sort Linked List

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given a linked list, sort it using insertion sort.

Approach

In insertion sort, the basic idea is to divide the list into a sorted and an unsorted part. Elements from the unsorted part are picked one by one and placed at their correct position in the sorted part until the whole list is sorted.

• Traverse the given linked list and insert each element at its correct position in the sorted list so that the resultant list remains sorted.
• Return the head of the sorted linked list.

Analysis

• Time Complexity: O(n2)
• Auxiliary Space Complexity: O(1)

Implementation

C++

/* This is the ListNode class definition

class ListNode {
public:
	int data;
	ListNode* next;

	ListNode(int data) {
		this->data = data;
		this->next = NULL;
	}
};
*/
ListNode* sortedHead;
void insertNode(ListNode* head) {
	if (sortedHead == NULL || sortedHead->data >= head->data) {
		head->next = sortedHead;
		sortedHead = head;
		return;
	}
	ListNode* currentNode = sortedHead;
	while (currentNode->next != NULL && currentNode->next->data < head->data) {
		currentNode = currentNode->next;
	}
	head->next = currentNode->next;
	currentNode->next = head;
	return;
}
ListNode* insertionSort(ListNode* head) {
	sortedHead = NULL;
	ListNode* currentNode = head;
	while (currentNode != NULL) {
		ListNode* nextNode = currentNode->next;
		insertNode(currentNode);
		currentNode = nextNode;
	}
	return sortedHead;
}

Java

/** This is the ListNode class definition

class ListNode {
	int data;
	ListNode next;

	ListNode(int data) {
		this.data = data;
		this.next = null;
	}
}
**/
class Solution {
	ListNode sortedHead;
	void insertNode(ListNode head) {
		if (sortedHead == null || sortedHead.data >= head.data) {
			head.next = sortedHead;
			sortedHead = head;
			return;
		}
		ListNode currentNode = sortedHead;
		while (currentNode.next != null && currentNode.next.data < head.data) {
			currentNode = currentNode.next;
		}
		head.next = currentNode.next;
		currentNode.next = head;
		return;
	}
	ListNode insertionSort(ListNode head) {
		sortedHead = null;
		ListNode currentNode = head;
		while (currentNode != null) {
			ListNode nextNode = currentNode.next;
			insertNode(currentNode);
			currentNode = nextNode;
		}
		return sortedHead;
	}
}