© Parineeth M R
Question 46. Given a linked list where the nodes can have the values 0 or 1 or 2, sort it in a single pass. For instance 2->1->0->0->2->0>1 should be sorted as 0->0->0->1->1->2->2
To sort the linked list in a single pass, we make use of the fact that there are only 3 possible values for the nodes in the linked list. So as we traverse the linked list, we can remove the nodes from the original linked list and append them into 3 separate linked lists based on the value of the nodes. At the end we can merge the 3 linked lists. The procedure we can use to solve the problem is as follows
1. Maintain the head and tail pointers for linked list-0 (will contain nodes with value 0), linked list-1 (will contain nodes with value 1) and linked list-2 (will contain nodes with value 2)
2. As we traverse through the original linked list, remove each node from the original linked list and add it to linked list-0 or linked list-1 or linked list-2 based on the value of the node.
3. At the end connect the tail of linked list-0 to the head of linked list-1 and the tail of linked list-1 to the head of linked list-2
C/C++
/*
head: array of head pointers of the separated lists
tail: array of tail pointers of the separated lists
cur_node: current node being processed
i: data value of the node
*/
void add_node(struct node *head[], struct node *tail[],
struct node *cur_node, int i)
{
cur_node->next = head[i];
head[i] = cur_node;
if (!tail[i])
tail[i] = cur_node;
}
/*first_node: first node in list to be sorted
num_distinct_values: number of distinct values in the nodes
Return value: head of the sorted list
*/
struct node * sort_list(struct node *first_node, int num_distinct_values)
{
struct node **head, **tail;
struct node *result = NULL, *cur_node, *next_node, *last_element;
int i;
if (!first_node)
return NULL;
head = (struct node**) calloc(num_distinct_values, sizeof(struct node*));
tail = (struct node**) calloc(num_distinct_values, sizeof(struct node*));
for (i = 0; i < num_distinct_values; ++i) {
head[i] = NULL;
tail[i] = NULL;
}
/*Partition the list into separate lists, (0-list, 1-list, 2-list)
based on the data in the node*/
cur_node = first_node;
while (cur_node) {
next_node = cur_node->next;
add_node(head, tail, cur_node, cur_node->data);
cur_node = next_node;
}
/*Connect the tail of first linked list with head of second linked list
and so on*/
result = head[0];
last_element = tail[0];
for (i = 1; i < num_distinct_values; ++i) {
if (!result)
result = head[i];
/*Link last element of previous list with head of current list*/
if (last_element)
last_element->next = head[i];
/*update the last element to the tail of current list*/
if (tail[i])
last_element = tail[i];
}
free(head);
free(tail);
return result;
}
Java
/*
head: array of heads of the separated lists
tail: array of tails of the separated lists
curNode: current node being processed
i: data value of the node
*/
public static void addNode(LinkedListNode[] head, LinkedListNode[] tail,
LinkedListNode curNode, int i) {
curNode.next = head[i];
head[i] = curNode;
if (tail[i] == null)
tail[i] = curNode;
}
/*firstNode: first node in the list to be sorted
numDistinctValues: number of distinct values
Return value: head of the sorted list
*/
public static LinkedListNode sortList(LinkedListNode firstNode,
int numDistinctValues) {
LinkedListNode[] head = new LinkedListNode[numDistinctValues];
LinkedListNode[] tail = new LinkedListNode[numDistinctValues];
LinkedListNode result = null;
if (firstNode == null)
return null;
int i;
for (i = 0; i < numDistinctValues; ++i) {
head[i] = null;
tail[i] = null;
}
/*Partition the list into separate lists (0-list, 1-list and 2-list)
based on the data in the node*/
LinkedListNode curNode = firstNode;
while (curNode != null) {
LinkedListNode nextNode = curNode.next;
addNode(head, tail, curNode, curNode.data);
curNode = nextNode;
}
/*Connect the tail of first linked list with head of second linked list
and so on*/
result = head[0];
LinkedListNode lastElement = tail[0];
for (i = 1; i < numDistinctValues; ++i) {
if (result == null)
result = head[i];
/*Link last element of previous list with head of current list*/
if (lastElement != null)
lastElement.next = head[i];
/*update the last element to the tail of current list*/
if (tail[i] != null)
lastElement = tail[i];
}
return result;
}
Python
#head: list having head nodes of all the separated linked lists #tail: list having tail nodes of all the separated linked lists #cur_node: current node being processed #i: data value of the node @staticmethod def add_node(head, tail, cur_node, i) : cur_node.next = head[i] head[i] = cur_node if (tail[i] == None): tail[i] = cur_node #first_node: first node in the linked list to be sorted #num_distinct_values: number of distinct values #Return value: head of the sorted linked list @staticmethod def sort_linked_list(first_node, num_distinct_values) : head = [None] * num_distinct_values tail = [None] * num_distinct_values result = None if (not first_node): return None #Partition the input linked list into separate linked lists #(0-list, 1-list and 2-list) based on the data in the node cur_node = first_node while (cur_node) : next_node = cur_node.next LinkedListNode.add_node(head, tail, cur_node, cur_node.data) cur_node = next_node #Connect the tail of first linked list with head of second linked list #and so on result = head[0] last_element = tail[0] for i in range(1, num_distinct_values): if (not result): result = head[i] #Link last element of previous linked list with head of #current linked list if (last_element): last_element.next = head[i] #update the last element to the tail of current linked list if (tail[i] != None): last_element = tail[i] return result