© 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

I hope you liked the article. ** I have written “The Big Book of Coding Interviews” in C/C++, Java and Python. If you are a US resident and want a free copy of the book**, please send an email to

Mention the programming language of your choice in the e-mail. I will mail the **Amazon Giveaway** link to you. **If you like the book please give your review comments on Amazon**. If you didn’t like the book, please mail me what you didn’t like and I will be glad to make the required changes.