About usWhy usInstructorsReviewsCostFAQContactBlogRegister for Webinar

Swap kth Nodes In Given Linked List

Given an integer singly linked list L of size n, and an integer k, you have to swap kth (1-indexed) node from the beginning, with kth node from the end. 

Note that you have to swap the nodes themselves, not just the contents.


Example

Input:

list: 1 -> 2 -> 3 -> 4 -> 7 -> 0 -> NULL

k: 2

Output:  

1 -> 7 -> 3 -> 4 -> 2 -> 0 -> NULL


Notes

Input Parameters: There are two arguments in input. First is an integer singly linked list L and second is an integer k. 

Output: Return resultant linked list resL, after swapping kth nodes of L. 


Constraints:

● 1 <= n <= 100000

● -2 * 10^9 <= value stored in any node <= 2 * 10^9

● 1 <= k <= n

● Try to access linked list nodes minimum number of times.


Solution

Have you considered "Try to access linked list nodes minimum number of times."?

If you have:

1) First find linked list length n.

2) Then find k-th node.

3) Then n-k+1-th node.

4) Swap the nodes. 

Then this is not the optimal solution.


Note that while finding the length of the list we could have found the k-th node in the same loop!

Now this is an optimal solution. 

Also there is another optimal solution possible and we have presented that in optimal_solution.cpp.


Time Complexity:

O(n).

Auxiliary Space Used:

O(1). 

Space Complexity:

O(n).

The input is O(n) and the auxiliary space used is O(1). So, O(n) + O(1) -> O(n).