Solution: Swapping Nodes in a Linked List

Let's solve the Swapping Nodes in a Linked List problem using the In-Place Manipulation of a Linked List pattern.

Statement

Given the linked list and an integer, k, return the head of the linked list after swapping the values of the kthk^{th} node from the beginning and the kthk^{th} node from the end of the linked list.

Note: We’ll number the nodes of the linked list starting from 11 to nn.

Constraints:

  • The linked list will have n number of nodes.
  • 11 \leq k \leq n 500\leq 500
  • 5000-5000 \leq Node.value 5000\leq 5000

Pattern: In-place Manipulation of a Linked List

We need to find the kthk^{th} node from the start of the linked list and the kthk^{th} node from the end of the linked list. We find the two nodes in the linked list using the in-place manipulation method. We use two pointers to traverse the linked list to find the kthk^{th} node from the start and the kthk^{th} node from the end of the linked list.

Once we’ve found these nodes, we swap their values without changing their positions.

Solution

There are multiple approaches to solving this problem: the three-pass, two-pass, and one-pass approaches. An efficient approach using a one-pass solution enables the swapping of kthk^{th} node from both ends of a linked list without determining the length of the list. The method involves advancing two pointers, curr and end, through the list, maintaining a gap of kk nodes between them. Initially, both pointers start from the head, with curr moving kk steps ahead. When the curr pointer reaches the kthk^{th} node, the end pointer starts moving from the head, while we use another pointer, front, to store the current position of curr. It continues the traversal by moving both curr and end pointers one step ahead until the curr reaches the end of the list. This ensures that the end pointer points the kthk^{th} node from the end of the list upon completing the traversal. The final step involves swapping the nodes pointed by the front and end pointers, effectively swapping the positions of the kthk^{th} nodes from both ends.

Now, let’s look at the different approaches to solving the problem.

The three-pass approach:

Let’s use two pointers, front and end, to help traverse a linked list and find the kthk^{th} node at the start and end of the linked list:

  • First pass: To find the kthk^{th} node at the start of the linked list, we traverse the linked list from the head to the kthk^{th} node using the front pointer.

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.