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

● -2 * 10^9

● 1

● 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).