Register for our webinar

1 hour

Step 1

Step 2

Congratulations!

You have registered for our webinar

Oops! Something went wrong while submitting the form.

Step 1

Step 2

Confirmed

You are scheduled with Interview Kickstart.

Redirecting...

Oops! Something went wrong while submitting the form.

Head of Career Skills Development & Coaching

*Based on past data of successful IK students

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.

Input:

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

k: 2

Output:

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

● -2 * 10^9

● 1

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

O(n).

O(1).

O(n).

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

Note: Input and Output will already be taken care of.

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.

Input:

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

k: 2

Output:

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

● -2 * 10^9

● 1

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

O(n).

O(1).

O(n).

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

**Attend our free webinar to amp up your career and get the salary you deserve.**

Hosted By

Ryan Valles

Founder, Interview Kickstart