Sponsored
Sponsored
This approach involves creating a new sorted list and inserting each element from the original list into the correct position in the new list, maintaining the sorted order.
Time Complexity: O(n2) in the worst case, where n is the number of nodes. This is due to iteratively inserting elements in order.
Space Complexity: O(1), as we use a constant amount of extra space other than the input list.
1#include <stdio.h>
2#include <stdlib.h>
3
4struct ListNode {
5 int val;
6 struct ListNode *next;
7};
8
9struct ListNode* insertionSortList(struct ListNode* head) {
10 if (head == NULL) return NULL;
11 struct ListNode* sortedHead = NULL;
12
13 while (head) {
14 struct ListNode* current = head;
15 head = head->next;
16 if (sortedHead == NULL || sortedHead->val >= current->val) {
17 current->next = sortedHead;
18 sortedHead = current;
19 } else {
20 struct ListNode* ptr = sortedHead;
21 while (ptr->next && ptr->next->val < current->val) {
22 ptr = ptr->next;
23 }
24 current->next = ptr->next;
25 ptr->next = current;
26 }
27 }
28 return sortedHead;
29}The code defines a function that sorts a linked list using insertion sort. It iterates over the original list, taking each node, and inserts it into the correct position in a new, sorted list. Specifically, it maintains a sorted list 'sortedHead' and iteratively places each node from the original list into this new list in sorted order.
Instead of creating a new list, this approach involves sorting the nodes within the existing linked list, rearranging the pointers directly.
Time Complexity: O(n2), due to each node insertion operation scanning the sequence.
Space Complexity: O(1), as no new nodes are created—existing nodes are relinked.
1#include
This C code keeps the sorted section within the same list, reordering nodes by adjusting the 'next' pointers appropriately. It makes sure the sorted part grows by including one element at a time, placed into the correct order.