Remove all non-leader nodes from a given singly linked list | CODING INTERVIEW ARCHIVES
Given a singly linked list of integers, you have to delete all non-leaders nodes from the list. By leader we mean a node for which all the nodes to its right are smaller in value than this node.
For example, in the list given as:
6 -> 9 -> 5-> 1
6 is a non-leader node as it has 9 in its right (which is greater than 6).
Algorithm:
Here, we are proposing a recursive solution for this problem.
On a side note, the following can be done:
1) Find the node with largest value.
2) Delete all nodes before the node with largest value
3) Set the node with largest value as head.
4) Call the recursive function on the reduced list.
Although the asymptotic complexity will remain the same, it will be slightly more memory efficient owing to reduced stack use.
Read full article from Remove all non-leader nodes from a given singly linked list | CODING INTERVIEW ARCHIVES
Given a singly linked list of integers, you have to delete all non-leaders nodes from the list. By leader we mean a node for which all the nodes to its right are smaller in value than this node.
For example, in the list given as:
6 -> 9 -> 5-> 1
6 is a non-leader node as it has 9 in its right (which is greater than 6).
Algorithm:
Here, we are proposing a recursive solution for this problem.
- If this node is the last node, set max as its data and return this node.
- Recursively, call for its neighbor.
- If value of this node it smaller than max, delete this node.
- Else if value of this is larger than max, update max as value of this node.
struct node* remove_non_leaders_util(struct node* head, int *max){
//base cases
if(head == NULL){
return NULL;
}
if(head->next == NULL){
*max = head->data;
return head;
}
struct node* temp = remove_non_leaders_util(head->next, max);
if(head->data < *max){
//delete node
head->data = temp->data;
head->next = temp->next;
free(temp);
return head;
}
else if(head->data > *max){
*max = head->data;
}
return head;
}
struct node* remove_non_leaders(struct node* head){
int max;
return remove_non_leaders_util(head, &max);
}
1) Find the node with largest value.
2) Delete all nodes before the node with largest value
3) Set the node with largest value as head.
4) Call the recursive function on the reduced list.
Although the asymptotic complexity will remain the same, it will be slightly more memory efficient owing to reduced stack use.
Read full article from Remove all non-leader nodes from a given singly linked list | CODING INTERVIEW ARCHIVES
