Pair Swap

PROBLEM STATEMENT

You are given a singly linked list of integers.

Your task is to swap every two adjacent nodes, and return the head of the modified, linked list.

For Example:

We have a linked list 1->2->3->4->5->6->7 and so on. You are supposed to swap pairs of a linked list like swap (1,2), (3,4), (5,6), and so on.

Note:

1. You may not modify the data in the list’s nodes; only nodes themselves may be changed. Because imagine a case where a node contains many fields, so there will be too much unnecessary swap.

2. If a pair of a node does not exist, then leave the node as it is.

Input format :

The input contains the elements of the singly linked list separated by a single space and terminated by -1. Hence, -1 would never be a list element.

Output format :

For each input, print a single line containing the same number of integers as in the list, in swapped order.

Note :

You do not need to print anything, it has already been taken care of just implement the given function.

Constraints :

0 <= N <= 5 * 10 ^ 5
-10 ^ 9 <= DATA <= 10 ^ 9 and DATA != -1

Where ‘N’ is the length of the linked list and 'DATA' is data in each node.

Time limit: 1 sec.

Approach 1

We traverse the linked list using recursion and consider two nodes at a time and swap their links and pass the next pair information to recursion.

The base case will be if the linked list is empty or contains one node then simply return the head.
Let’s say we have two elements of nodes for a particular pair.

		    'FIRST' = 'HEAD'
		'SECOND' = 'HEAD' -> 'NEXT'

Store the node of the list after two-node of “HEAD” because only links of these two nodes (“FIRST” and “SECOND”) are going to change for the current pair. Let’s say “REMAININGNODE”.

	'REMAINING-NODE' = 'SECOND' -> 'NEXT'

For the current pair, our new head will be “SECOND”. So store that as “NEW-HEAD”.

		'NEW-HEAD' = 'SECOND'

Change the next of the second node as the head. Because after swapping, the “FIRST” node will be the “SECOND” node, and the “SECOND” node will be “FIRST”.

	   'SECOND' -> 'NEXT' = 'FIRST'

Call recursively for “REMAININGNODE” and store the modified head (what we will get from recursion) as “FIRST→NEXT”.
Return the modified head of the linked list, i.e. “NEWHEAD”.

Try Problem

Approach 2

Our idea is to swap the links of each pair from the “HEAD” of the list until we reach the end of the list or there is only one element left.

Here, note that after the swap, the head of our list may change if the size of the input list is larger than one, so we are using a dummy node as a placeholder to splice our result list. In this way, we can start with the dummy node and check if there exists a pair of nodes after the current pointer we perform a swap on their links.

Steps:

Let’s say the next node of our dummy node contains the head of the list.

	'DUMMY' -> 'NEXT'='HEAD'

And we start with our dummy node. Let’s say we have a “CURR” node.

		'CURR' = 'DUMMY';

We will perform operation until we reach the end, i.e. “CURR→NEXT” become “NULL” or there is only one element left, i.e. “CURR→NEXT→NEXT” become “NULL”.
1. Swap “CURR→NEXT” to “CURR→NEXT→NEXT”
2. Now go to the next pair of the list, i.e. “CURR→NEXT→NEXT”
Finally “DUMMY→NEXT” has the “HEAD” of the modified, linked list. Simply return “DUMMY→NEXT”.

Try Problem