Swapping Nodes in a Linked List

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
4 upvotes
Asked in companies
AmazonMicrosoftServiceNow

Problem statement

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].
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
2
2
1 4 5 6 9 -1
1
4 5 7 8 10 -1
Sample Output 1:
CORRECT
CORRECT
Explanation:
For the first test case, 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.

For the second test case, after swapping 1st node from the start i.e, 4 with 1st node from the end i.e, 10 we get the final list as: 10 -> 5 -> 7 -> 8 -> 4 -> NULL.
Sample Input 2:
1
2
-2 3 5 -7 9 -1
Sample Output 2:
CORRECT
Hint

Find the position of the kth node from the beginning and the kth node from the end.

Approaches (3)
Brute Approach

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

O(N), where N is the number of the nodes in the given list.
 

We are iterating through the list thrice to find the length of the list, the kth node, and the (n-k)th node. Hence the overall time complexity is O(N).

Space Complexity

O(1).

 

Constant space is being used. Hence the overall space complexity is O(1).

Code Solution
(100% EXP penalty)
Swapping Nodes in a Linked List
Full screen
Console