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