Site icon Study Algorithms

Reverse a Linked List in pairs.

Question: Write a program to reverse a Linked List in pairs. That means we should reverse the 1st and 2nd numbers, 3rd and 4th numbers and so on.

Input: 4, 8, 15, 16, 23, 42

Output: 8, 4, 16, 15, 42, 23

The basic idea behind solving this problem is that we need to traverse the entire list and we need to keep on swapping the values of 2 adjacent nodes.
Since we need to reverse the values in pairs, it is also clear that we need to move 2 nodes at a time till we reach the end of the list.

This can be achieved in two ways:-

RECURSIVE APPROACH:-

//Recursive Version to reverse in pairs
void reverseInPairRecursive(struct node * head)
{
	//creating a temporary node
	struct node * temp = (struct node *)malloc(sizeof(struct node));

	/*
	the terminating condition for the recursion
	this is also valid if the list is empty
	OR has only one element.
	*/
	if(head == NULL || head -> next == NULL)
		return;
	else
	{
		// reverse the first pair
		temp -> data = head -> data;
		head -> data = head -> next -> data;
		head -> next -> data = temp -> data;

		// calling the method recursively
		reverseInPairRecursive(head -> next -> next);
	}
}

ITERATIVE APPROACH:-

//Iterative version to reverse in pairs
void reverseInPairIterative(struct node * head)
{
	// creating temporary variables
	struct node * temp = (struct node *)malloc(sizeof(struct node));
	struct node * current = head;

	// check for NULL and the NEXT of a node for NULL
	while(current != NULL && current -> next != NULL)
	{
		//swap the pair
		temp -> data = current -> data;
		current -> data = current -> next -> data;
		current -> next -> data = temp -> data;

		//Advance the current pointer by 2 nodes
		current = current -> next -> next;
	}
}

Here is a working implementation of the code. You can use your favorite editor to open it (Wordpad, Notepad++, gEdit…)

Exit mobile version