Category: Linked Lists

Interleave two linked lists

admin / / Data Structures, Linked Lists

© Parineeth M R

Question 10. Interleave two linked lists

Let’s consider two linked lists, L1 having the members A->B->C->D and L2 having the members X->Y->Z. Interleaving the two linked lists will result in the single linked list A->X->B->Y->C->Z->D, wherein the first node of L2 is placed next to the first node of L1, second node of L2 is placed next to second node of L1 and so on. If the sizes of the two linked lists are m and n, then interleaving can be done in O(m+n)

C/C++


/* 
n1: head of the first linked list
n2: head of the second linked list
Return value: head of the result interleaved linked list
*/
struct node* interleave_lists( struct node *n1, struct node *n2)
{
	struct node *result,  *temp1, *temp2;

	if (!n1) {
		return n2; /*If linked list1 is empty, return n2 */
	}
	
	if (!n2) {
		return n1; /*If linked list2 is empty, return n1*/
	}
	
	/*Process the two linked lists*/
	result = n1;
	while (n1 != NULL && n2 != NULL) {
		temp1 = n1->next;
		temp2 = n2->next;

		/*Place node of second linked list next to the node 
		of the first linked list*/
		if (n1->next)
			n2->next = n1->next;
		n1->next = n2;

		n1 = temp1;
		n2 = temp2;
	}
	return result;
}

Java


/* 
n1: head of the first linked list
n2: head of the second linked list
Return value: head of the result interleaved linked list
*/
public static LinkedListNode interleaveLists( LinkedListNode n1, 
					LinkedListNode n2) {

	if (n1 == null) {
		return n2; /*If linked list1 is empty, return n2 */
	}

	if (n2 == null) {
		return n1; /*If linked list2 is empty, return n1*/
	}

	/*Process the two linked lists*/
	LinkedListNode result = n1;
	while (n1 != null && n2 != null) {
		LinkedListNode temp1 = n1.next;
		LinkedListNode temp2 = n2.next;

		/*Place node of second linked list next to the node 
		of the first linked list*/
		if (n1.next != null)
			n2.next = n1.next;
		n1.next = n2;

		n1 = temp1;	
		n2 = temp2;	
	}
	return result;
}

Python


#n1: head of the first linked list
#n2: head of the second linked list
#Return value: head of the result interleaved linked list
@staticmethod
def interleave(n1, n2):
	if (not n1): 
		return n2 #If linked list1 is empty, return n2 

	if (not n2): 
		return n1 #If linked list2 is empty, return n1

	#Process the two linked lists
	result = n1
	while (n1 and n2): 
		temp1 = n1.next
		temp2 = n2.next

		#Place node of second linked list next to the node of 
		#the first linked list
		if (n1.next):
			n2.next = n1.next
		
		n1.next = n2

		n1 = temp1
		n2 = temp2

	return result

Find cycle in Linked List

admin / / Data Structures, Linked Lists

© Parineeth M R

Question 9. Find out if there is a cycle in a linked list. Also find the node where the cycle begins

We can maintain the is_visited field in each node. Initially the is_visited field in all the nodes is set to 0. When a node is traversed in the linked list, the is_visited field is changed from 0 to 1. While traversing the linked list, the moment we encounter a node whose is_visited field is already 1, we know that there is a cycle in the linked list and the cycle begins at this node. The drawback of this approach is that it uses additional memory.

To solve the problem without using additional memory, we use the following idea. Suppose two runners take part in a race, one of them being faster than the other, the faster runner will overtake the slower runner as soon as the race starts. If the race track is a loop, then later in the race, the faster runner will again meet the slower runner and overtake him. Similarly, we can traverse the linked list using a fast pointer and a slow pointer. At each step, the fast pointer is moved ahead by 2 nodes, whereas the slow pointer is moved ahead by 1 node. If there is a loop in the linked list, the two pointers will meet at a common node.

To find where the loop starts, we need to do the following: Let n1 be the fast pointer and n2 be the slow pointer. When n1 and n2 meet, initialize a third pointer n3 to point to the beginning of the linked list. So n1 is ahead of n3 in the linked list. Now ignore n2 and advance n1 and n3 one node at a time. The node where n1 and n3 meet is where the loop starts.

C/C++

/*head: first node of the linked list 
Return value: first node in loop if loop exists, NULL otherwise
*/
struct node* find_loop( struct node *head) 
{
	struct node *n1 = head, *n2 = head, *n3;
	int found_loop = 0;

	/*n1 is the fast pointer. So advance it by two steps
	n2 is slow pointer. So advance it by one step
	*/
	while (n1 != NULL) {
		n1 = n1->next;
		if (n1) {
			n1 = n1->next;
			n2 = n2->next;
		}

		/*If n1 and n2 meet then there is a loop in the linked list*/
		if (n1 == n2) {
			found_loop = 1;
			break;
		}
	}
	
	if (!found_loop)
		return NULL;

	/*Find the beginning of the loop*/
	n3 = head;
	while (n1 != n3) {
		n1 = n1->next;
		n3 = n3->next;
	}
	
	return n1;
}

Java


/*head: first node of the linked list 
Return value: first node in loop if loop exists, null otherwise
*/
public static LinkedListNode findLoop( LinkedListNode head)  {
	LinkedListNode n1 = head, n2 = head;
	boolean foundLoop = false;

	/*n1 moves fast. So advance it by two steps
	n2 is slow. So advance it by one step
	*/
	while (n1 != null) {
		n1 = n1.next;
		if (n1 != null) {
			n1 = n1.next;
			n2 = n2.next;
		}

		/*If n1 and n2 meet then there is a loop in the linked list*/
		if (n1 == n2) {
			foundLoop = true;
			break;
		}
	}

	if (!foundLoop)
		return null;

	/*Find the beginning of the loop*/
	LinkedListNode n3 = head;
	while (n1 != n3) {
		n1 = n1.next;
		n3 = n3.next;
	}

	return n1;
}

Python


#head: first node of the linked list 
#Return value: first node in loop if loop exists, None otherwise
@staticmethod
def find_loop(head): 
	n1 = n2 = head
	found_loop = False

	#n1 moves fast. So advance it by two steps
	#n2 is slow. So advance it by one step
	while (n1): 
		n1 = n1.next
		if (n1): 
			n1 = n1.next
			n2 = n2.next
	
		#If n1 and n2 meet then there is a loop in the linked list
		if (n1 == n2): 
			found_loop = True
			break
	
	if (not found_loop):
		return None
	
	#Find the beginning of the loop
	n3 = head
	while (n1 != n3):
		n1 = n1.next
		n3 = n3.next

	return n1

Find where two linked lists merge

admin / / Data Structures, Linked Lists

© Parineeth M R

Question 8. Two linked lists merge at a common node. Given the heads of the two linked lists, find the node where the linked lists merge. For instance, the two linked lists ABCXYZ and PQXYZ merge at node X

Using a brute force approach, we can pick each node in the first linked list and compare it with every node in the second linked list in sequential order. If we get a match, then we have found the first common node between the two linked lists. If one linked list has m nodes and the other has n nodes, this takes O(mn) time.
However there are better techniques to solve the problem. Two approaches which can perform better than the brute force approach are described below

Approach 1: Marking the nodes
An extra field is maintained in each node to indicate if the node has been visited or not. Initially the nodes in both linked lists have the field set to 0 indicating that they have not yet been visited. The nodes of the first linked list are then traversed and the visited field in the first linked list nodes is set to 1 indicating that they have been visited. Then the nodes of the second linked list are traversed in sequential order. As soon as we encounter a node in the second linked list with the visited field set to 1, we have found the first node that is common to both the linked lists. The time taken by this approach is O(m+n) and it requires additional space in each node to store the visited field

Approach 2: Counting
The lengths of the two linked lists are first computed. Let m be the number of nodes in the longer linked list and n be the number of nodes in the shorter linked list. n1 is made to point to the head of the longer linked list and n2 is made to point to the head of the shorter linked list. The absolute difference in the lengths of the two linked lists m-n is then computed. n1 is advanced in the longer linked list by m-n nodes. Now the number of remaining nodes starting from n1 in the longer linked list is equal to the number of nodes in the shorter linked list. If n1 and n2 point to the same node, we have found the first common node. If not, we advance n1 and n2 by one node in their respective linked lists and compare them. This process is repeated till we get a match or we reach the end of the linked lists. The time taken by this approach is also O(m+n) and requires no additional space. So this approach is the preferred solution and is given below.

C/C++


/*
head1: first node of linked list1
head2: first node of linked list2
Return value: first common node between the two linked lists
*/
struct node * find_intersection_node(struct node * head1, struct node *head2)
{
	struct node *n1, *n2;
	int length1, length2, diff;

	/*Find the length of the two linked lists*/
	length1 = find_length(head1);
	length2 = find_length(head2);

	/*store head of the longer linked list in n1 and head of shorter 
	linked list in n2*/
	if (length1 >= length2) {
		n1 = head1;
		n2 = head2;
	} else {
		n1 = head2;
		n2 = head1;
	}

	/*Find the difference in length of the two linked lists. Then advance
	n1 by the difference*/
	diff = abs(length1 - length2);
	while (diff > 0) {
		n1 = n1->next;
		--diff;
	}

	/*Go on comparing the nodes in linked list1 starting from n1 and
	linked list2 starting from n2 till n1 and n2 match*/
	while (n1 && n2 && n1 != n2) {
		n1 = n1->next;
		n2 = n2->next;
	}

	/*n1 will have the common node if it exists, otherwise n1 will be NULL*/
	return n1;
}

Java


/*
head1: first node of linked list1
head2: first node of linked list2
Return value: first common node between the two linked lists
*/
public static LinkedListNode findIntersectionNode(LinkedListNode head1, 
				LinkedListNode head2) {
	/*Find the length of the two linked lists*/
	int length1 = findLength(head1);
	int length2 = findLength(head2);
	LinkedListNode n1, n2;

	/*store head of the longer linked list in n1 and head of 
	shorter linked list in n2*/
	if (length1 >= length2) {
		n1 = head1;
		n2 = head2;
	} else {
		n1 = head2;
		n2 = head1;
	}

	/*Find the difference in length of the two linked lists. Then advance
	n1 by the difference*/
	int diff = Math.abs(length1 - length2);
	while (diff > 0) {
		n1 = n1.next;
		--diff;
	}

	/*Go on comparing the nodes in linked list1 starting from n1 and
	linked list2 starting from n2 till n1 and n2 match*/
	while (n1 != null && n2 != null && n1 != n2) {
		n1 = n1.next;
		n2 = n2.next;
	}

	/*n1 will have the common node if it exists, otherwise n1 will be null*/
	return n1;
}

Python


#head1: first node of linked list1
#head2: first node of linked list2
#Return value: first common node between the two linked lists 
@staticmethod
def find_intersection_node(head1, head2):
	#Find the length of the two linked lists
	length1 = LinkedListNode.find_length(head1)
	length2 = LinkedListNode.find_length(head2)

	#store head of the longer linked list in n1 and head of 
	#shorter linked list in n2
	if (length1 >= length2) :
		n1 = head1
		n2 = head2
	else :
		n1 = head2
		n2 = head1
	
	#Find the difference in length of the two linked lists. Then advance
	#n1 by the difference
	diff = abs(length1 - length2)
	while (diff > 0) :
		n1 = n1.next
		diff = diff - 1
	
	#Go on comparing the nodes in linked list1 starting from n1 and
	#linked list2 starting from n2 until n1 and n2 match
	while (n1 and n2 and n1 != n2) :
		n1 = n1.next
		n2 = n2.next
	
	#n1 will have the common node if it exists, otherwise n1 will be None
	return n1

Rotate a linked list

admin / / Data Structures, Linked Lists

© Parineeth M R

Question 7. Rotate a linked list by k positions

Consider the linked list A->B->C->D->E. If we rotate the linked list by k = 2 positions, then the linked list will become D->E->A->B->C. To perform the rotation we do the following:

1. Locate the kth node from the end (let’s call this node the pivot). If k = 2, we have to locate the second last node which in this case is D.

2. Make the node previous to the pivot point to NULL. So in this case C will point to NULL.

3. Traverse till the end of the linked list and make the last node point to the head of the linked list. So the last node E will point to the head A.

4. Make the pivot the head of the new linked list. So D will now become the new head.

Note that if k = length of linked list, then after rotation we end up with the original linked list. So we apply the formula, k = k % length to figure out the actual rotation required.

C/C++


/*
head: first node of the linked list
k: by how many positions the linked list should be rotated
length: number of nodes in the linked list
Return value: first node of the rotated linked list
*/
struct node* rotate_list(struct node *head, int k, int length)
{
	struct node *pivot, *prev, *last;

	/*If there are 0 or 1 nodes in the linked list, then simply return*/
	if (length < 2)
		return head;

	/*If we shift by k times, then we get back the same linked list. So we 
	just have to shift k % length times*/
	k = k % length;

	/*If k is 0, then no need to shift*/
	if (k == 0)
		return head;

	/*Find the kth node from the end. If k = 1, then pivot will have
	the last node and prev will be the node previous to last node*/
	prev = NULL;
	pivot = find_kth_node_from_end(head, k, length, &prev);

	/*Find the last node in the linked list*/
	last = pivot;
	while (last->next)
		last = last->next;

	/*Make the last node point to head and the node previous to pivot
	point to NULL*/
	last->next = head;
	prev->next = NULL;

	/*pivot will be the new head*/
	return pivot;
}

Java


/*
head: first node of the linked list
k: by how many positions the linked list should be rotated
length: number of nodes in the linked list
Return value: first node of the rotated linked list
*/
public static LinkedListNode rotateList(LinkedListNode head, int k, int length) {
	LinkedListNode[] prevArray = new LinkedListNode[1];

	/*If there are 0 or 1 nodes in the linked list, then simply return*/
	if (length < 2)
		return head;

	/*If we shift by k times, then we get back the same linked list. So we 
	just have to shift k % length times*/
	k = k % length;

	/*If k is 0, then no need to shift*/
	if (k == 0)
		return head;

	/*Find the kth node from the end. If k = 1, then pivot will have
	the last node and prev will be the node previous to last node*/
	LinkedListNode pivot = findKthNodeFromEnd(head, k, length, prevArray);
	LinkedListNode prev = prevArray[0];

	/*Find the last node in the linked list*/
	LinkedListNode last = pivot;
	while (last.next != null)
		last = last.next;

	/*Make the last node point to head and the node previous to pivot
	point to null*/
	last.next = head;
	prev.next = null;

	/*pivot will be the new head*/
	return pivot;
}

Python


#head: first node of the linked list
#k: by how many positions the linked list should be rotated
#length: number of nodes in the linked list
#Return value: first node of the rotated linked list
@staticmethod
def rotate(head, k, length):
	#If there are 0 or 1 nodes in the linked list, then simply return
	if (length < 2):
		return head

	#If we shift by k times, then we get back the same linked list. 
	#So we just have to shift k % length times
	k = k % length

	#If k is 0, then no need to shift
	if (k == 0):
		return head

	#Find the kth node from the end. If k = 1, then pivot will have
	#the last node and prev will be the node previous to last node
	pivot, prev = LinkedListNode.find_kth_node_from_end(head, k, length)

	#Find the last node in the linked list
	last = pivot
	while (last.next):
		last = last.next

	#Make the last node point to head and the node previous to pivot
	#point to None
	last.next = head
	prev.next = None

	#pivot will be the new head
	return pivot

Remove duplicates from linked list

admin / / Data Structures, Linked Lists

© Parineeth M R

Question 6. Remove duplicates from a linked list

For removing duplicates, we can try two approaches
1. Use brute force. Pick each node (let’s call it current node) in the linked list, then check the nodes that occur after the current node and remove those nodes that are identical to the current node. The time complexity is O(n2). We don’t need additional memory.

2. Use a hash table. As we traverse the linked list, we store the data of the nodes in the hash table. If the data of a node has already been stored in the hash table, then it is a duplicate and we delete the node from the linked list. The time complexity is O(n) but we will use additional memory because of the hash table.
The code for the brute force approach is given below

C/C++


/*
head: first node in the linked list
*/
void remove_duplicates(struct node *head)
{
	struct node *cur_node, *iter_node, *prev_node;

	/*If there are 0 or 1 nodes in linked list, then simply return*/
	if (head == NULL || head->next == NULL)
		return;
			
	cur_node = head;
	while (cur_node) {
		/*Iterate from node after cur_node to the end of the linked list*/
		iter_node = cur_node->next;
		prev_node = cur_node;

		while (iter_node) {
			if (cur_node->data == iter_node->data) {
				/*iter_node is a duplicate of cur_node. So remove it*/
				prev_node->next = iter_node->next;
				free(iter_node);
				iter_node = prev_node->next;
			} else {
				prev_node = iter_node;
				iter_node = iter_node->next;
			}
		}
		
		cur_node = cur_node->next;
	}
}

Java


/*
head: first node in the linked list
*/
public static void removeDuplicates(LinkedListNode head) {
	/*If there are 0 or 1 nodes in linked list, then simply return*/
	if (head == null || head.next == null)
		return;
		
	LinkedListNode curNode = head;
	while (curNode != null) {
		/*Iterate from node after curNode to the end of linked list*/
		LinkedListNode iterNode = curNode.next;
		LinkedListNode prevNode = curNode;

		while (iterNode != null) {
			if (curNode.data == iterNode.data) {
				/*iterNode is a duplicate of curNode. 
				so remove it*/
				prevNode.next = iterNode.next;
				iterNode = iterNode.next;
			} else {
				prevNode = iterNode;
				iterNode = iterNode.next;
			}
		}
	
		curNode = curNode.next;
	}
}

Python


#head: first node in the linked list
@staticmethod
def remove_duplicates(head): 
	#If there are 0 or 1 nodes in linked list, then simply return
	if (not head or not head.next):
		return
		
	cur_node = head
	while (cur_node) :
		#Iterate from node after cur_node to the end of the linked list
		iter_node = cur_node.next
		prev_node = cur_node

		while (iter_node) :
			if (cur_node.data == iter_node.data) :
				#iter_node is a duplicate of cur_node. so 
				#remove it
				prev_node.next = iter_node.next
				iter_node = iter_node.next
			else :
				prev_node = iter_node
				iter_node = iter_node.next

			
		cur_node = cur_node.next

Delete node given pointer to it

admin / / Data Structures, Linked Lists

© Parineeth M R

Question 5. Delete a node in a linked list given only a pointer/reference to that node

Let us say that we are given only a pointer n1 to the node that needs to be deleted. We don’t know the node previous to n1. If we delete the node that n1 points to, then we can’t update the next pointer of the node preceding n1. So we can’t directly delete n1, but we have to employ a trick to do the job.
To solve the problem, let n2 be the pointer to the node next to n1. We copy n2->data into n1->data. We also copy n2->next into n1->next. Now n1 points to a node that is exactly identical to the node pointed by n2. Now instead of deleting n1, we delete n2. This achieves the required result.
This solution will not work if the node being deleted is the last node in the linked list and the last node points to NULL. One possible approach to make this solution work for all nodes in the linked list is to use a circular linked list.

C/C++


/* 
n1: pointer to the node to be deleted
Return value: 0 on success, -1 on failure
*/
int delete_node(struct node *n1)
{
	struct node *n2;

	if (n1->next) {
		/*Get the pointer to the next node*/
		n2 = n1->next;

		/*Copy the contents of the next node into the current node*/
		n1->data = n2->data;
		n1->next = n2->next;

		/*Free the next node*/
		free(n2);

		/*Return indicating the operation is successful*/
		return 0;
	}

	/*return indicating the operation failed*/
	return -1;
}

Java


/* 
n1: the node to be deleted
Return value: true on success, false on failure
*/
public static boolean deleteNode(LinkedListNode n1) {

	if (n1.next != null) {
		/*Get the next node*/
		LinkedListNode n2 = n1.next;

		/*Copy the contents of the next node into the current node*/
		n1.data = n2.data;
		n1.next = n2.next;

		/*Return indicating the operation is successful*/
		return true;
	}

	/*return indicating the operation failed*/
	return false;
}

Python


#n1: the node to be deleted
#Return value: True on success, False on failure
@staticmethod
def delete_node(n1):
	if (n1.next): 
		#Get the next node
		n2 = n1.next

		#Copy the contents of the next node into the current node
		n1.data = n2.data
		n1.next = n2.next

		#Return indicating the operation is successful
		return True

	#return indicating the operation failed
	return False

Swap kth node from beginning and end

admin / / Data Structures, Linked Lists

© Parineeth M R

Question 4. Swap the kth node from the end with the kth node from the beginning of a linked list

If the length of the linked list is n, then k can take values from 1 to n. We can solve the problem in O(n) using the following steps:
1. Find the kth node from the start of the linked list (k1) and its previous node (prev1).
2. Find the kth node from the end of the linked list (k2) and its previous node (prev2).
3. Swap k1 and k2. While swapping we have to handle three possible cases:
• k1 and k2 are identical. In this case we don’t have to swap
• k1 and k2 are neighbors (either k1->next = k2 or k2->next = k1)
• k1 and k2 are not neighbors

Note that if k is 1, then we have to swap the head of the linked list with the tail of the linked list. In this case, the head of the linked list will change. Also note that the node k1 may lie before or after k2. For instance, if linked list length is 10 and k = 3, then k1 is before k2. But if linked list length is 10 and k = 9, then k1 is after k2

C/C++


/*Helper function which swaps two neighbors n1 and n2
head: first node in the linked list
prev: node previous to n1
n1: first node to be swapped
n2: second node to be swapped. n2 occurs immediately after n1
Return value: head of the result linked list after swapping neighbors
*/
struct node* swap_neighbors(struct node *head, struct node *prev, 
			struct node *n1, struct node *n2)
{
	/*Swap n1 and n2*/
	n1->next = n2->next;
	n2->next = n1;

	if (prev) {
		prev->next = n2;
	} else {
		head = n2; /*If prev doesn't exist, update head to n2*/
	}
	return head; 
}
 
/*Main function for swapping the kth node from beginning and end
head: first node in the linked list
k: which node in the linked list should be swapped
length: number of nodes in the linked list
Return value: head of the result linked list on success, NULL on error
*/
struct node* swap_kth_node(struct node *head, int k, int length)  {
	struct node  *temp;
	struct node *k1, *k2, *prev1, *prev2;

	if (!head || k < 1 || k > length)
		return NULL;

	prev1 = prev2 = NULL;

	/*k1 is the kth node from begining and prev1 is previous to k1*/
	k1 = find_kth_node_from_begin(head, k, &prev1);

	/*k2 is the kth node from end and prev2 is previous to k2*/
	k2 = find_kth_node_from_end(head, k, length, &prev2);

	if (k1 == NULL || k2 == NULL)
		return NULL; /*the k value is incorrect*/

	if (k1 == k2)
		return head; /*both nodes are the same. So no need to swap*/
	
	/*Handle the case where k1 and k2 are neighbors and return*/
	if (k1->next == k2) 
		return swap_neighbors(head, prev1, k1, k2);

	if (k2->next == k1) 
		return swap_neighbors(head, prev2, k2, k1);

	/*k1 and k2 are not neighbors. So swap k1.next with k2.next*/
	temp = k1->next;
	k1->next = k2->next;
	k2->next = temp;

	if (prev1) {
		prev1->next = k2; 
	} else  {
		head = k2; /* After swap, k2 becomes new head*/
	}

	if (prev2) {
		prev2->next = k1; 
	} else  {
		head = k1; /* After swap, k1 becomes new head */
	}

	return head;
}

Java


/*Helper function which swaps two neighbors n1 and n2
head: first node in the linked list
prev: node previous to n1
n1: first node to be swapped
n2: second node to be swapped. n2 occurs immediately after n1
Return value: head of the result linked list after swapping neighbors
*/
public static LinkedListNode swapNeighbors(LinkedListNode head,  
		LinkedListNode prev, LinkedListNode n1, LinkedListNode n2) {
	/*Swap n1 and n2*/
	n1.next = n2.next;
	n2.next = n1;

	if (prev != null) {
		prev.next = n2;
	} else {
		head = n2; /*If prev doesn't exist, update head to n2*/
	}

	return head; 
}
 
/*Main function for swapping the kth node from beginning and end
head: first node in the linked list. 
k: which node in the linked list should be swapped
length: number of nodes in the linked list
Return value: head of the result linked list on success, null on error
*/
public static LinkedListNode swapKthNode(LinkedListNode head, int k, 
					int length)  {
	LinkedListNode[] prevArray = new LinkedListNode[1];

	if (head == null || k < 1 || k > length)
		return null;

	/*k1 is the kth node from begining and prev1 is previous to k1*/
	LinkedListNode k1 = LinkedListNode.findKthNodeFromBegin(head, k, prevArray);
	LinkedListNode prev1 = prevArray[0];

	/*k2 is the kth node from end and prev2 is previous to k2*/
	LinkedListNode k2 = LinkedListNode.findKthNodeFromEnd(head, k, prevArray);
	LinkedListNode prev2 = prevArray[0];

	if (k1 == null || k2 == null)
		return null; /*the k value is incorrect*/

	if (k1 == k2)
		return head; /*both nodes are the same. So no need to swap*/

	/*If k1 and k2 are neighbors, then handle this case and return*/
	if (k1.next == k2) 
		return swapNeighbors(head, prev1, k1, k2);

	if (k2.next == k1) 
		return swapNeighbors(head, prev2, k2, k1);

	/*k1 and k2 are not neighbors. So swap k1.next with k2.next*/
	LinkedListNode temp = k1.next;
	k1.next = k2.next;
	k2.next = temp;

	if (prev1 != null) {
		prev1.next = k2; 
	} else  {
		head = k2; /* After swap, k2 becomes new head*/
	}

	if (prev2 != null) {
		prev2.next = k1; 
	} else  {
		head = k1; /* After swap, k1 becomes new head */
	}

	return head;
}

Python

#Helper function which swaps two neighbors n1 and n2
#head: first node in the linked list
#prev: node previous to n1
#n1: first node to be swapped
#n2: second node to be swapped. n2 occurs immediately after n1
#Return value: head of the result linked list after swapping neighbors
@staticmethod
def swap_neighbors(head, prev, n1, n2):
	#Swap n1 and n2
	n1.next = n2.next
	n2.next = n1

	if (prev): 
		prev.next = n2
	else: 
		head = n2 #If prev doesn't exist, update head to n2

	return head 

 
#Main function for swapping the kth node from beginning and end
#head: first node in the linked list. 
#k: which node in the linked list should be swapped
#length: number of nodes in the linked list
#Return value: head of the result linked list on success, None on error
@staticmethod
def swap_kth_node(head,  k,  length):  
	if (not head or k < 1 or k > length):
		return None

	#k1 is the kth node from begining and prev1 is previous to k1
	k1, prev1 = LinkedListNode.find_kth_node_from_begin(head, k)
	
	#k2 is the kth node from end and prev2 is previous to k2
	k2, prev2 = LinkedListNode.find_kth_node_from_end(head, k)

	if (not k1 or not k2):
		return None #the k value is incorrect

	if (k1 == k2):
		return head #both nodes are the same. So no need to swap

	#If k1 and k2 are neighbors, then handle this case and return
	if (k1.next == k2): 
		return LinkedListNode.swap_neighbors(head, prev1, k1, k2)

	if (k2.next == k1): 
		return LinkedListNode.swap_neighbors(head, prev2, k2, k1)

	#k1 and k2 are not neighbors. So swap k1.next with k2.next
	temp = k1.next
	k1.next = k2.next
	k2.next = temp

	if (prev1): 
		prev1.next = k2 
	else:  
		head = k2 #After swap, k2 becomes new head

	if (prev2): 
		prev2.next = k1 
	else:  
		head = k1 #After swap, k1 becomes new head

	return head

Find kth node from the end

admin / / Data Structures, Linked Lists

© Parineeth M R

Question 3. Find the kth node from the end of a linked list

We can treat the last node in the linked list as either the 0th node from the end or we can treat the last node as the 1st node from the end. So k can begin from 0 or 1. In the function below, we are treating the last node as the 1st node from the end. To find the kth node from the end, we first find the length of the linked list. Then we again traverse through the linked list to find the (length – k +1)th node from the beginning which corresponds to the kth node from the end. If the length of the linked list is n, then in the worst case we will access 2n nodes. The time complexity is O(n)

C/C++


/* 
head: first node of the linked list
k: node position from the end. k starts from 1 onwards
Return value: kth node from end if it exists, NULL otherwise
*/
struct node* find_kth_node_from_end(struct node *head, int k)
{
	struct node *n1;
	int i, length;

	length = 0;
	n1 = head;
	while (n1 != NULL) {
		length++;
		n1 = n1->next;
	}

	n1 = head;
	for (i = 1; i <= length; ++i) {
		if (i == length - k + 1) {
			return n1; 	/*n1 is the kth node from end. So return it*/
		}
		n1 = n1->next;
	}

	/*k value passed doesn't match with the linked list. So return NULL */
	return NULL;
}

Java


/* 
head: the first node of the linked list
k: node position from the end. k starts from 1 onwards
Return value: kth node from end if it exists, null otherwise
*/
public static LinkedListNode findKthNodeFromEnd(LinkedListNode head, int k) {
	int length = 0;

	LinkedListNode n1 = head;
	while (n1 != null) {
		length++;
		n1 = n1.next;
	}

	n1 = head;
	for (int i = 1; i <= length; ++i) {
		if (i == length - k + 1) {
			return n1; 	/*n1 is the kth node from end. So return it*/
		}
		n1 = n1.next;
	}

	/*k value passed doesn't match with the linked list. So return null */
	return null;

}

Python


#head: the first node of the linked list
#k: node position from the end. k starts from 1 onwards
#Return value: kth node from end if it exists, None otherwise
@staticmethod
def find_kth_node_from_end(head, k):
	length = 0
	n1 = head
	while (n1): 
		length += 1
		n1 = n1.next

	n1 = head
	for i in range(1, length + 1): 
		if (i == length - k + 1): 
			return n1 	#n1 is the kth node from end. So return it
	
		n1 = n1.next

	#k value passed doesn't match with the linked list. So return None
	return None

Reverse every K nodes

admin / / Data Structures, Linked Lists

© Parineeth M R

Question 2. Reverse every k nodes in a linked list. So if the input is A->B->C->D->E->F->G->H and k is 3, then the output should be C->B->A->F->E->D->H->G

Both recursive and non-recursive solutions exist to reverse every k nodes with O(n) time complexity. Although the recursive solution takes more space, we will use it here since it is simpler. If there are n nodes in the linked list, we reverse the first k nodes and then recursively process the remaining n – k nodes. Let the linked list be A->B->C->D->E->F->G->H and k = 3. The diagram below illustrates the technique

C/C++


/* 
head: the first node of the linked list
k: how many nodes should be reversed
Return value: first node of the new linked list after reversing every k nodes
*/
struct node * k_reverse_list(struct node *head, int k)
{
	struct node *cur_node,  *prev_node, *temp_node;
	int i = 0;

	if (!head || k == 0)
		return head;

	cur_node = head;
	prev_node = NULL;

	while (cur_node && i < k) {
		/*Store the next node in a temporary variable*/
		temp_node = cur_node->next;

		/*Reverse the link */
		cur_node->next = prev_node;

		/*Update the previous node to the current node */
		prev_node = cur_node;

		/*Proceed to the next node in the original linked list*/
		cur_node = temp_node;

		++i;
	}

	/*
	We have reversed k nodes. cur_node points to the (k+1)th node
	and head points to the kth node.
	Now recursively process the remaining nodes from cur_node onwards 
	and assign the result to head->next.
	*/
	if (cur_node)
		head->next = k_reverse_list(cur_node, k);

	/*prev_node will point to first node in linked list after reversal*/
	return prev_node;
}

Java


/* 
head: first node of the linked list
k: how many nodes should be reversed
Return value: first node of the new linked list after reversing every k nodes
*/
public static LinkedListNode kReverseList(LinkedListNode head, int k) {
	int i = 0;

	if (head == null || k == 0)
		return head;

	LinkedListNode curNode = head;
	LinkedListNode prevNode = null;

	while (curNode != null && i < k) {
		/*Store the next node in a temporary variable*/
		LinkedListNode tempNode = curNode.next;

		/*Reverse the link */
		curNode.next = prevNode;

		/*Update the previous node to the current node */
		prevNode = curNode;

		/*Proceed to the next node in the original linked list*/
		curNode = tempNode;

		++i;
	}

	/*
	We have reversed k nodes. So curNode refers to the (k+1)th node.
	and head now refers to the kth node.
	Now recursively process the remaining nodes from curNode onwards 
	and assign the result to head.next.
	*/
	if (curNode != null)
		head.next = kReverseList(curNode, k);

	/*prevNode will refer to first node in linked list after reversal*/
	return prevNode;
}

Python


#head: first node of the linked list
#k: how many nodes should be reversed
#Return value: first node of the new linked list after reversing every k nodes
@staticmethod
def  k_reverse(head, k):
	if (not head or k == 0):
		return head

	cur_node = head
	prev_node = None
	i = 0
	while (cur_node and i < k): 
		#Store the next node in a temporary variable
		temp_node = cur_node.next

		#Reverse the link 
		cur_node.next = prev_node

		#Update the previous node to the current node
		prev_node = cur_node

		#Proceed to the next node in the original linked list
		cur_node = temp_node

		i += 1

	#We have reversed k nodes. So cur_node refers to the (k+1)th node
	#and head refers to the kth node.
	#Now recursively reverse the remaining nodes from cur_node onwards 
	#and assign the result to head.next.
	if (cur_node):
		head.next = LinkedListNode.k_reverse(cur_node, k)

	#prev_node will refer to first node in the linked list after reversal
	return prev_node

Reverse a Linked List

admin / / Data Structures, Linked Lists

© Parineeth M R

Question 1. Reverse a linked list

A linked list can be reversed without using recursion by maintaining 3 nodes: prev_node, cur_node and next_node. As we traverse the linked list, we update the 3 nodes and the links in the linked list are reversed. The time complexity is O(n).

C/C++

/*Reverses the linked list without using recursion
head: first node in the original linked list 
Return value: the first node of the reversed linked list
*/
struct node* reverse_linked_list(struct node *head) {
	struct node *cur_node, *prev_node, *next_node;

	cur_node = head;
	prev_node = NULL;

	while (cur_node) {
		/*Store the next node in a temporary variable*/
		next_node = cur_node->next;

		/*Reverse the link so that current node points to the previous node*/
		cur_node->next = prev_node;

		/*Update the previous node to the current node */
		prev_node = cur_node;

		/*Proceed to the next node in the original linked list*/
		cur_node = next_node;
	}

	/*
	Once the linked list has been reversed, prev_node will be
	pointing to the new head. So return it
	*/
	return prev_node;
}

Java


/*Reverses the linked list without using recursion
head: first node in the original linked list 
Return value: the first node of the reversed linked list
*/
public static LinkedListNode reverseLinkedList(LinkedListNode head) {
	LinkedListNode curNode = head;
	LinkedListNode prevNode = null;

	while (curNode != null) {
		/*Store the next node in a temporary variable*/
		LinkedListNode nextNode = curNode.next;

		/*Reverse the link */
		curNode.next = prevNode;

		/*Update the previous node to the current node */
		prevNode = curNode;

		/*Proceed to the next node in the original linked list*/
		curNode = nextNode;
	}

	/*
	Once the linked list has been reversed, prevNode will have
	the new head. So return it
	*/
	return prevNode;
}

Python


#Reverses the linked list without using recursion
#head: first node in the original linked list 
#Return value: the first node of the reversed linked list
@staticmethod
def reverse(head):
	cur_node = head
	prev_node = None

	while (cur_node):
		#Store the next node in a temporary variable
		next_node = cur_node.next

		#Reverse the link 
		cur_node.next = prev_node

		#Update the previous node to the current node
		prev_node = cur_node

		#Proceed to the next node in the original linked list
		cur_node = next_node


	#Once the linked list has been reversed, prev_node will be
	#referring to the new head. So return it
	return prev_node