Last Updated: 25 Sep, 2021
Swapping Nodes in a Linked List
Moderate
Asked in companies
You are given a head node of linked list ‘head’ and an integer ‘K’. You have to swap the ‘K’ node from the beginning and the ‘K’ node from the end.
You need to return the head of the updated linked list.
Note:
You need to perform swapping of nodes in the given linked list. Do not swap the values.
For example:
If the given list is:[1 -> 4 -> 5 -> 6 -> 9 -> NULL] and ‘K’ is 2, then after swapping 2nd node from the start i.e, 4 with 2nd node from the end i.e, 6 we get the final list as: [1 -> 6 -> 5 -> 4 -> 9 -> NULL].
Input Format:
The first line contains an integer 'T' which denotes the number of test cases.
The first line of each test case contains a single integer ‘K’ which denotes the position of the nodes to be swapped.
The second line of each test case contains space-separated integers denoting the values of nodes of the Linked List. The Linked List is terminated with -1.
Output Format:
For each test case, print “CORRECT” if the nodes are swapped in the given list. Otherwise, print “INCORRECT”.
Print the output of each test case in a separate line.
Constraints:
1 <= T <= 10
1 <= N <= 10 ^ 6
-10^9 <= Node.Data <= 10^9 and Node.Data != -1
1 <= K <= N
The linked list is 1-indexed.
Time Limit: 1 sec
Note:
You do not need to input or print anything, as it has already been taken care of. Just implement the given function.
Approaches
In this approach, we will use two pointers, say begin and end. We will also use two other nodes prevBegin and prevEnd, to store the previous begin and end node, respectively. The variable begin would point to the kth node from the beginning, and the end would point to the kth node from the end. To find the position of the begin we will traverse the list up to the k node. To find the end position, we will first find the length of the list and then traverse up to (length of the list - k) nodes.
Then, we will swap the node pointed by the begin with the node pointed by the end by breaking old links and creating new links.
Algorithm:
- Initialize a variable n with value 0.
- Initialize a variable current that will be equal to the head node.
- Iterate while current is not null
- increment n by 1
- current = current.next
- Initialize a variable begin that will be equal to the head node.
- Initialize a variable prevBegin that will be equal to the null.
- Iterate i from 1 to k
- begin = begin.next
- Initialize a variable end that will be equal to the head node.
- Initialize a variable prevEnd that will be equal to the null.
- Iterate i from 1 to n-k
- end = end.next
- If prevBegin is not null
- prevBegin.next = begin
- If prevEnd is not null
- prevEnd = begin
- Initialize a variable temp that will be equal to begin.next
- begin.next = end.next
- end.next = temp
- If k is equal to 1
- head = end
- If k is equal to n
- head = begin
- Finally, return head.
This approach is the same as the above. The difference is that instead of iterating the list thrice in this approach, we will iterate it twice. While finding the length of the list, when we come across the (k - 1)th node, we will set prevBegin equal to it, and when we come across the kth node, we will set begin equal to it.
Algorithm:
- Initialize a variable n with value 0.
- Initialize a variable current that will be equal to the head node.
- Initialize a variable begin that will be equal to the head node.
- Initialize a variable prevBegin that will be equal to the null.
- Iterate while current is not null
- increment n by 1
- If n is equal to k - 1
- prevBegin = current
- If n == k
- begin = current
- current = current.next
- Initialize a variable end and prevEnd that will be equal to the null.
- Iterate i from 1 to n-k
- prevEnd = end
- end = end.next
- If prevBegin is not null
- prevBegin.next = begin
- If prevEnd is not null
- prevEnd = begin
- Initialize a variable temp that will be equal to begin.next
- begin.next = end.next
- end.next = temp
- If k is equal to 1
- head = end
- If k is equal to n
- head = begin
- Finally, return head.
This approach is also the same as the above. The difference is that we will iterate only once instead of iterating the list twice in this approach. The method of finding the position of begin will be the same as above. To find the end position, we will use the fact that if a node says n1 is exactly k nodes behind another node n2, then when the node n2 reaches the end, the node n1 will still be k nodes behind, i.e., at the kth node from the end.
Algorithm:
- Initialize a variable n with value 0.
- Initialize a variable current that will be equal to the head node.
- Initialize a variable begin and prevBegin that will be equal to the null.
- Initialize a variable end and prevEnd that will be equal to the null.
- Iterate while current is not null
- increment n by 1
- If end is not null
- prevEnd = end
- end = end.next
- If n is equal to k - 1
- prevBegin = current
- If n is equal to k
- begin = current
- end = head
- current = current.next
- If prevBegin is not null
- prevBegin.next = begin
- If prevEnd is not null
- prevEnd = begin
- Initialize a variable temp that will be equal to begin.next
- begin.next = end.next
- end.next = temp
- If k is equal to 1
- head = end
- If k is equal to n
- head = begin
- Finally, return head.