Sort a linked list containing 3 different types of elements

© 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