Home Linked List Reverse a Linked List in pairs.

Reverse a Linked List in pairs.

by nikoo28
0 comment

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…)

0 comment

You may also like

Enclose codes in [code lang="JAVA"] [/code] tags

This site uses Akismet to reduce spam. Learn how your comment data is processed.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More