Pair Swap

Posted: 28 Sep, 2020
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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