Swap Nodes in Pairs

Moderate
0/80
Average time to solve is 40m
profile
Contributed by
34 upvotes
Asked in companies
OLX GroupAmazonMicrosoft

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.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
11 21 13 14 15 -1
Sample Output 1:
21 11 14 13 15 -1
Explanation of the Sample Input1:
Swap 11 with 21 then swap 13 with 14 and 15 has no pair so leave that node as it is.
Sample Input 2:
-13 14 -21 18 -20 30 -1
Sample Output 2:
14 -13 18 -21 30 -20 -1
Explanation of the Sample Input 2:
Swap -13 with 14 then swap -21 with 18 and then swap -20 to with 30.
Hint

How can you change the next pointer of the first node and second node without changing their values such that they are swapped?

Approaches (2)
Using Recursion

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”.
Time Complexity

O(N), where ‘N’ is the number of nodes in the linked list.

 

It takes O(N) time to traverse the entire linked list. And swapping takes constant cost.

Space Complexity

O(N), where ‘N’ is the number of nodes in the linked list.

 

We are iterating in the list through the recursion, and for each pair, we have to push the function into the call stack. So there can be total “N/2” pairs, and the recursion call stack can grow up to “N/2” depth. So overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Swap Nodes in Pairs
Full screen
Console