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.
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 ; } }Video 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.