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 node from the beginning and the node from the end of the linked list.
Note: We’ll number the nodes of the linked list starting from to .
Constraints:
- The linked list will have
n
number of nodes. -
k
n
-
Node.value
Pattern: In-place Manipulation of a Linked List
We need to find the node from the start of the linked list and the 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 node from the start and the 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 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 nodes between them. Initially, both pointers start from the head, with curr moving steps ahead. When the curr pointer reaches the 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 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 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 node at the start and end of the linked list:
- First pass: To find the node at the start of the linked list, we traverse the linked list from the head to the node using the
front
pointer.
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.