Swap kth node from beginning and end

© 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