Swapping Nodes in a Linked List
MedPrompt
You are given the head of a linked list, and an integer k.
Return the head of the linked list after swapping the values of the kth node from the beginning and the kth node from the end (the list is 1-indexed).
Example 1:
Input: head = [1,2,3,4,5], k = 2
Output: [1,4,3,2,5]Example 2:
Input: head = [7,9,6,6,7,8,3,0,9,5], k = 5
Output: [7,9,6,6,8,7,3,0,9,5]
Constraints:
- The number of nodes in the list is
n. 1 <= k <= n <= 1050 <= Node.val <= 100
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves converting the linked list into an array (or a List in Java). Once the list is in an array format, we can use indices to directly access the k-th element from the beginning and the k-th element from the end. After swapping their values, the original linked list, whose nodes are stored in the array, is modified.
Algorithm
- Create a
java.util.ArrayListto store the nodes of the linked list. - Iterate through the linked list from the
head, adding eachListNodeto theArrayList. - Let
nbe the size of theArrayList. The k-th node from the beginning is at indexk-1. - The k-th node from the end is at index
n-k. - Retrieve the two nodes:
node1 = list.get(k-1)andnode2 = list.get(n-k). - Swap the
valfields ofnode1andnode2. - Return the original
headof the list.
Walkthrough
The core idea is to trade space for simplicity. By traversing the linked list once and storing all its nodes in a dynamic array like ArrayList, we can leverage random access capabilities. The k-th node from the start is simply the element at index k-1, and the k-th node from the end is at index n-k (where n is the total number of nodes). After getting references to these two nodes, we can swap their values directly.
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */import java.util.ArrayList;import java.util.List; class Solution { public ListNode swapNodes(ListNode head, int k) { List<ListNode> nodes = new ArrayList<>(); ListNode current = head; while (current != null) { nodes.add(current); current = current.next; } int n = nodes.size(); ListNode node1 = nodes.get(k - 1); ListNode node2 = nodes.get(n - k); int temp = node1.val; node1.val = node2.val; node2.val = temp; return head; }}Complexity
Time
O(n), where n is the number of nodes in the linked list. We traverse the list once to populate the array, which takes O(n) time. Accessing elements in the `ArrayList` by index takes O(1) time.
Space
O(n), as we need an auxiliary `ArrayList` to store all the n nodes of the linked list.
Trade-offs
Pros
Simple to understand and implement.
Direct access to nodes once they are in an array makes finding the target nodes trivial.
Cons
High space complexity, which can be an issue for very large lists.
Less efficient than in-place algorithms that do not require extra data structures.
This approach avoids using extra space by traversing the list multiple times. First, we find the total length of the list. With the length, we can calculate the position of the k-th node from the end. Then, we traverse the list again to find both the k-th node from the beginning and the k-th node from the end and swap their values.
Algorithm
- First, traverse the list to find its length,
n. - The k-th node from the beginning is found by traversing
k-1steps from thehead. Let's call thisnode1. - The k-th node from the end is the
(n - k + 1)-th node from the beginning. We can find this node by traversingn-ksteps from thehead. Let's call thisnode2. - Once both
node1andnode2are found, swap their values. - Return the original
head.
Walkthrough
This method is space-efficient. The first pass is dedicated to calculating the total number of nodes, n. Knowing n, the position of the k-th node from the end can be determined as n - k + 1 from the beginning. With the positions of both nodes known, we perform two more traversals from the head of the list to locate each node. The first traversal goes k-1 steps to find the first node, and the second traversal goes n-k steps to find the second node. Finally, we swap their values.
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */class Solution { public ListNode swapNodes(ListNode head, int k) { // Pass 1: Find the length of the list int n = 0; ListNode current = head; while (current != null) { n++; current = current.next; } // Find the first node (k-th from beginning) ListNode node1 = head; for (int i = 0; i < k - 1; i++) { node1 = node1.next; } // Find the second node (k-th from end, which is n-k+1 from beginning) ListNode node2 = head; for (int i = 0; i < n - k; i++) { node2 = node2.next; } // Swap the values int temp = node1.val; node1.val = node2.val; node2.val = temp; return head; }}Complexity
Time
O(n), where n is the number of nodes. The list is traversed once to find the length (O(n)), and then up to two more times to find the nodes (O(k) and O(n-k)). The total time complexity is O(n) + O(k) + O(n-k) = O(2n) which simplifies to O(n).
Space
O(1), as we only use a few pointers and variables to keep track of the nodes and length, regardless of the list size.
Trade-offs
Pros
Space efficient, using constant extra space.
Relatively easy to reason about and implement correctly.
Cons
Requires multiple passes over the linked list, which is less efficient than a single-pass solution in terms of total operations.
This is the most optimal approach. It finds both nodes in a single pass using pointers. We first advance one pointer k-1 steps to locate the k-th node from the beginning. Then, we start a second pointer from the head and advance both pointers together until the first pointer reaches the end of the list. At this point, the second pointer will be at the k-th node from the end.
Algorithm
- Initialize a
currentpointer tohead. Also initialize two pointers,node1andnode2, which will eventually point to the nodes to be swapped. - First, find the k-th node from the beginning. Move the
currentpointerk-1steps forward. - After the loop,
currentpoints to the k-th node. Assign this node tonode1. - Now,
node1is found. To findnode2(the k-th node from the end), initializenode2tohead. - Continue traversing with
currentfrom its current position until it reaches the end of the list. Simultaneously, movenode2forward from the head. - When
currentreaches the last node,node2will be pointing to the k-th node from the end. - Swap the values of
node1andnode2. - Return
head.
Walkthrough
This elegant solution uses the two-pointer technique to solve the problem in a single pass. We first identify the k-th node from the beginning. Let's call it node1. We use a pointer, say current, and advance it k-1 times from the head. Now, current is at node1. To find the k-th node from the end, we use another pointer, node2, initialized at the head. We then continue to advance current to the end of the list. For every step current takes, we also advance node2. The gap between node2 and the end of the list will be the same as the gap between the head and node1's initial position. Thus, when current reaches the last node, node2 will be at the k-th position from the end.
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */class Solution { public ListNode swapNodes(ListNode head, int k) { ListNode current = head; // Move current k-1 steps to find the k-th node from the beginning for (int i = 0; i < k - 1; i++) { current = current.next; } // This is the first node to be swapped ListNode node1 = current; // This will be the second node to be swapped, start it from the head ListNode node2 = head; // Move current to the end of the list. // As current moves, move node2. This maintains a gap of n-k between them. // When current reaches the end, node2 will be at the k-th position from the end. while (current.next != null) { current = current.next; node2 = node2.next; } // Swap the values int temp = node1.val; node1.val = node2.val; node2.val = temp; return head; }}Complexity
Time
O(n), where n is the number of nodes. We traverse the list only once. The first loop runs `k-1` times, and the second loop runs `n-k` times. The total number of steps is `(k-1) + (n-k) = n-1`, which constitutes a single pass.
Space
O(1). We only use a constant number of pointers, regardless of the list size.
Trade-offs
Pros
Most efficient in terms of both time and space.
Traverses the list only once, minimizing the number of node visits.
Cons
The logic with two pointers moving at different stages might be slightly more complex to grasp initially compared to the two-pass approach.
Solutions
Solution
/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int val=0, ListNode next=null) { * this.val = val; * this.next = next; * } * } */ public class Solution { public ListNode SwapNodes ( ListNode head , int k ) { ListNode fast = head ; while (-- k > 0 ) { fast = fast . next ; } ListNode p = fast ; ListNode slow = head ; while ( fast . next != null ) { fast = fast . next ; slow = slow . next ; } ListNode q = slow ; int t = p . val ; p . val = q . val ; q . val = t ; return head ; } }/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode swapNodes ( ListNode head , int k ) { ListNode fast = head ; while (-- k > 0 ) { fast = fast . next ; } ListNode p = fast ; ListNode slow = head ; while ( fast . next != null ) { fast = fast . next ; slow = slow . next ; } ListNode q = slow ; int t = p . val ; p . val = q . val ; q . val = t ; return head ; } }/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode * swapNodes ( ListNode * head , int k ) { ListNode * fast = head ; while ( -- k ) { fast = fast -> next ; } ListNode * slow = head ; ListNode * p = fast ; while ( fast -> next ) { fast = fast -> next ; slow = slow -> next ; } ListNode * q = slow ; swap ( p -> val , q -> val ); return head ; } };# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution : def swapNodes ( self , head : Optional [ ListNode ], k : int ) -> Optional [ ListNode ]: fast = slow = head for _ in range ( k - 1 ): fast = fast . next p = fast while fast . next : fast , slow = fast . next , slow . next q = slow p . val , q . val = q . val , p . val return headVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.