Posted: 28 Sep, 2020
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.
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.
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.
You do not need to print anything, it has already been taken care of just implement the given function.
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.
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”.
Prime Digit Sum
Posted: 17 Apr, 2022
Insertion In Circular Linked List
Posted: 21 Apr, 2022
Insertion In A Singly Linked List
Posted: 22 Apr, 2022
Deletion In Doubly Linked List
Posted: 22 Apr, 2022
Insertion In Doubly Linked List
Posted: 24 Apr, 2022