The problem is it sort a linked list with O(N log N) time complexity and O(1) space complexity.
I was thinking what sort algorithm to use. I learned only heapsort and merge-sort algorithms.
heapsort algorithm in an in-place algorithm where we will not use any extra space other than recursive stack. Thought of implementing the heapsort for linked list.
Before implementing heapsort for linked list, I wrote the heapsort algorithm for arrays. Below is the one:
void heapsort(int *ar, int num){
/* if array has one only one node, no action
if more than one , build heap,
take the root node from heap and swap with the last node of array.
As the swap operation, disturbed the heap,
repeat building heaps by avoid last swapped nodes.
repeat all the nodes except one node swapped */
while (num-1>0){
build_max_heap(ar, num);
swap(ar, 0, num-1);
num--;
}
}/* build Max heap */
/* Heap is a binary tree
Max heap has a property that
every node value should be greater than its children.
Min heap has a property that
every node value should be lesser than its children.
So to build a heap we need to check its node value with its children.
Leaf nodes will not have children. So checking is not required for those nodes.
Any binary tree will have half of its nodes as leaf nodes as tree starts from one root node, then two children, then those two children will have another 4 children, etc.
In heap it is assumed that node i will have its children at locations 2*i and 2*i + 1
Now lets build a max heap
*/
void build_max_heap(int *ar, int num){
int num_parents = num/2;
/* consider only nodes with children
start building heap from bottom up approach
Suppose if the number of elements are 9.
node 1 has children at node 2 and node 3
node 2 has children at node 4 and node 5
node 3 has children at node 6 and node 7
node 4 has children at node 8 and node 9
node 5 till node 9 will not have children.
So these nodes (last 5 nodes) need not be compared with empty children
these are leaf nodes
Now compare the nodes which its children.
This comparison of nodes can be started from the nodes just above leaf nodes
This comparison of nodes functionality we can call heapify
Call the heapify function for each parent node */
while (num_parents > 0){
max_heapify(ar, num_parents, num);
num_parents--;
}
}/* function to heapify/construct the heap :)
node_i and number of nodes are passed to this function,
get the node_i's children : node_2*i and node2*i+1
Take the max value of these 3 nodes and assign it to node_i.
Suppose the node_2*i is having max value,
Now to build heap we swapped the node_i with node_2*i.
Now that heap of node_2*i got disturbed, this heapify should be called for node_2*i.
As this is called recursively, there are cases where this node_2*i or node_i may not have children or these are leaf nodes.
In these cases we just need to return */
void max_heapify(int *ar, int node_i, int num){
/* node_i at array will be at node_i-1 position */
int tmp_loc = node_i;
if (((2*node_i) < num) && (ar[2*node_i-1] > ar[tmp_loc-1]))
tmp_loc = 2*node_i;
if ((((2*node_i) +1) < num) && (ar[2*node_i] > ar[tmp_loc-1]))
tmp_loc = (2*node_i)+1;
if (tmp_loc != node_i){
swap(ar, tmp_loc-1, node_i-1);
max_heapify(ar, tmp_loc, num);
}
}inline void swap(int *ar, int p1, int p2){
int tmp = ar[p1];
ar[p1] = ar[p2];
ar[p2] = tmp;
}
Then written the below version for linked list:
struct ListNode *get_nth_node(struct ListNode *head, int n);
struct ListNode * build_max_heap_list(struct ListNode *head, int num);
struct ListNode *max_heapify_list(struct ListNode *hd, int node_i, int num);/* function to get the nth node of the list */
struct ListNode *get_nth_node(struct ListNode *head, int n){
int ii=1;
struct ListNode *tmp=head;
while (tmp!=NULL){
if (ii==n) return tmp;
tmp = tmp->next;ii++;
}
return NULL;
}struct ListNode * heapsort_list(struct ListNode *head){
int num=0;
struct ListNode *tmp = head, *tmp1;
/* getting total number of nodes */
while (tmp){
num++; tmp=tmp->next;}
/* Build heap for every n elements, after building the heap swap the first element with the last element, then decrement the heap size by not considering the last element */
while (num-1>0){
head = build_max_heap_list(head, num);
if (num-1 >1){
struct ListNode *n;
/* this needs one traversal */
tmp = get_nth_node(head, num-1);
tmp1 = tmp->next; tmp->next = head;
n = tmp1->next;
tmp1->next = head->next;
head->next = n;
head = tmp1;
} else {
struct ListNode *n;
tmp = head->next;
if (head->next) head->next = head->next->next;
else head->next = NULL;
tmp->next = head; head = tmp;
}
num--;
}
return head;
}struct ListNode * build_max_heap_list(struct ListNode *head, int num){
int num_parents = num/2;
while (num_parents > 0){
head = max_heapify_list(head, num_parents, num);
num_parents--;
}
return head;
}
struct ListNode *max_heapify_list(struct ListNode *head, int node_i, int num) {
int tmp_loc = node_i;
struct ListNode *tmp, *child_node, *tmp_prev=NULL, *child_prev, *m;
if (node_i > 1){
/* This is to get the parent node, one traversal adds up */
tmp_prev = get_nth_node(head, node_i-1);
m = tmp = tmp_prev->next;
}
else { m = tmp = head; }
if ((2*node_i) <= num){
/* This is to get the child node , it can be included part of the above traversal */
child_prev = get_nth_node(tmp, node_i);
child_node = child_prev->next;
if (tmp->val < child_node->val) { tmp_loc = 2*node_i;
m = child_node;}
}
if ((((2*node_i) +1) <= num) &&
(m->val < child_node->next->val)) {
tmp_loc = (2*node_i)+1; child_prev=child_node;
child_node = child_node->next;
m = child_node;
}
if (tmp_loc != node_i){
/* swap the tmp and child_node nodes */
if (tmp_prev){
/* tmp prev of next should be child_node */
/* child_prev of next should be tmp */
tmp_prev->next = child_node;
m = child_node->next;
child_node->next = tmp->next;
child_prev->next = tmp;
tmp->next =m;
}else if (child_prev != head) {
/* head should be child_node */
m = head->next;
child_prev->next = head;
head->next = child_node->next;
child_node->next = m;
head = child_node;
}else { /* case where consecutive elements at head should be swapped */
tmp->next = child_node->next;
child_node->next = tmp;
head = child_node;
} head = max_heapify_list(head, tmp_loc, num);
}
return head;
}
The above code is not easy. While swapping the elements in a linked list, we should take care of the head is pointing to the first element, no NULLs added in the middle, make sure of getting the previous node instead of the to-be swapped node.
Lots of traversals are required here:
- each parent node needs traversal
- To build a heap , we go through minimum of n/2 nodes that needs minimum of n/2 traversals.
- For each swap of last node, another traversal also required.
We can do some optimizations, still I think this algorithm is not suitable to linked list sorting.
Please provide your comments.
