Search⌘ K
Home
Courses
Coderust: Hacking the Coding Interview

Sort Linked List Using Insertion Sort

Explore how to implement insertion sort on a linked list by moving nodes from the original list to a new sorted list. Understand the step-by-step process, time and space complexities, and practice this fundamental linked list algorithm.

We'll cover the following...

Statement

We’re given the head pointer of a linked list. Sort the linked list in ascending order using insertion sort. Return the new head pointer of the sorted linked list.

Example

If the given linked list is 29 -> 23 -> 82 -> 11, then the sorted list should be 11 -> 23 -> 29 -> 82.

g head head a 29 head->a sorted sorted NULL NULL b 23 a->b c 82 b->c d 11 c->d d->NULL a1 11 sorted->a1 NULL2 NULL b1 23 a1->b1 c1 29 b1->c1 d1 82 c1->d1 d1->NULL2

Sample input

[29, 23, 82, 11]

Expected output

[11, 23, 29, 82]

Try it yourself

...