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.
list: 1 -> 2 -> 3 -> 4 -> 7 -> 0 -> NULL
1 -> 7 -> 3 -> 4 -> 2 -> 0 -> NULL
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.
● 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.
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.
The input is O(n) and the auxiliary space used is O(1). So, O(n) + O(1) -> O(n).