Algorithm
Problem Name: 147. Insertion Sort List
Given the head of a singly linked list, sort the list using insertion sort, and return the sorted list's head.
The steps of the insertion sort algorithm:
- Insertion sort iterates, consuming one input element each repetition and growing a sorted output list.
- At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list and inserts it there.
- It repeats until no input elements remain.
The following is a graphical example of the insertion sort algorithm. The partially sorted list (black) initially contains only the first element in the list. One element (red) is removed from the input data and inserted in-place into the sorted list with each iteration.
Example 1:
Input: head = [4,2,1,3] Output: [1,2,3,4]
Example 2:
Input: head = [-1,5,3,4,0] Output: [-1,0,3,4,5]
Constraints:
- The number of nodes in the list is in the range
[1, 5000]. -5000 <= Node.val <= 5000
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* insertionSortList(struct ListNode* head) {
if (head == NULL) return NULL;
struct ListNode *dummy = (struct ListNode *)malloc(sizeof(struct ListNode));
dummy->val = 0;
dummy->next = NULL;
struct ListNode *t = dummy;
struct ListNode *p;
struct ListNode *min_ptr, *min_prev; /* prev node of min node */
int min_val;
p = head;
while (p) {
min_val = p->val;
min_ptr = p;
min_prev = NULL;
struct ListNode *q = p->next;
struct ListNode *prev = p;
while (q) {
if (q->val < min_val) {
min_val = q->val;
min_prev = prev;
min_ptr = q;
}
prev = q;
q = q->next;
}
if (p == min_ptr) { /* if min node is p, we don't need to modify list */
p = p->next; /* just move forward p, and the min_prev is still */
} /* NULL now. */
else {
min_prev->next = min_ptr->next; /* take node from list */
}
t->next = min_ptr;
t = t->next;
}
t->next = NULL;
t = dummy->next;
free(dummy);
return t;
}
Input
Output
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public ListNode insertionSortList(ListNode head) {
ListNode dummy = new ListNode(0);
ListNode curr = head;
ListNode prev = dummy;
ListNode next = null;
while (curr != null) {
next = curr.next;
while (prev.next != null && prev.next.val < curr.val) {
prev = prev.next;
}
curr.next = prev.next;
prev.next = curr;
prev = dummy;
curr = next;
}
return dummy.next;
}
}
Input
Output
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const insertionSortList = function(head) {
const dummy = new ListNode()
dummy.next = head
let insert = dummy
let cur = head
while (cur && cur.next) {
if (cur.val < cur.next.val) {
cur = cur.next
continue
}
insert = dummy
while (insert.next.val < cur.next.val) {
insert = insert.next
}
const temp = cur.next
cur.next = temp.next
temp.next = insert.next
insert.next = temp
}
return dummy.next
}
Input
Output
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def insertionSortList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
ref, ref.next, n = ListNode(-float("inf")), head, 0
while head:
inserted, curr, prev, n = ListNode(head.val), ref.next, ref, n+1
for i in range(n-1):
if inserted.val= n-2: curr.next = None
break
else:
prev, curr = curr, curr.next
if i == n-2: prev.next = inserted
head = head.next
return ref.next
Input
Output