Swapping Nodes in a Linked List solution and explanation
Google
9 more videos on this problem
Swapping Nodes in a Linked List - Leetcode 1721 - PythonNeetCodeIO · 5:31 · 17K views
Leetcode - Swapping Nodes in a Linked List (Python)Timothy H Chang · 2:40 · 2K views
1721. Swapping Nodes in a Linked List (Leetcode Medium)Programming Live with Larry · 8:33 · 995 views
1721. Swapping Nodes in a Linked List | Leetcode | City Coder | 14th MarchCity Coder · 5:47 · 712 views
Swapping Nodes in a Linked List - Leetcode 1721 - PythonTechError · 4:36 · 653 views
Swapping Nodes in a Linked List (Leetcode 1721)Coding Interviews · 16:27 · 581 views
Swapping Nodes in a Linked List | LeetCode 1721 | Coders CampCoders Camp · 4:01 · 543 views
1721. Swapping Nodes in a Linked List | Single Pass | LeetCode Daily Challenge POTDDeep Tech · 8:32 · 419 views
Daily Leetcode #734: Apr 04, 2022 - 1721. Swapping Nodes in a Linked ListProgramming Live with Larry · 6:09 · 256 views
Daily Leetcode #348: Mar 14, 2021 - 1721. Swapping Nodes in a Linked ListProgramming Live with Larry · 6:07 · 167 views
The problem
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
Approach overview
Problem Overview: Given the head of a singly linked list and an integer k, swap the values of the kth node from the beginning and the kth node from the end. The list structure must remain intact, so you typically swap node values rather than rearranging node pointers.
Approach 1: Two Pass Technique (O(n) time, O(1) space)
This method first computes the total length of the linked list. Once you know the length n, the node to swap from the end becomes the (n - k + 1)th node from the beginning. Perform one traversal to count nodes, then a second traversal to locate both the kth node and the (n - k + 1)th node. After locating them, swap their values. The logic is simple and easy to reason about during interviews because you separate the tasks: measure the list, then locate the targets. Time complexity is O(n) due to two linear passes, while space complexity stays O(1) since only a few pointers are used.
Approach 2: Single Pass with Two Pointers (O(n) time, O(1) space)
This optimized approach finds both nodes in a single traversal using the two pointers technique. First iterate until you reach the kth node from the start and keep a reference to it. Then start a second pointer from the head while continuing the traversal with the current pointer until the end. When the first pointer reaches the last node, the second pointer will land exactly on the kth node from the end. Swap the values of these two nodes. This technique works because the gap between the pointers remains constant after the kth node is identified. It completes the entire operation in one pass with O(n) time and O(1) space.
Recommended for interviews: The single-pass two pointer method is usually the expected optimal solution. It demonstrates control over pointer movement and efficient traversal of a linked list. The two-pass method is still valuable because it shows a clear understanding of indexing in linked structures and often serves as the stepping stone toward the optimized approach.
Approach 1: Approach 1: Two Pass Technique
This approach involves two passes through the linked list. In the first pass, we determine the kth node from the beginning. In the second pass, we find the kth node from the end. Once we have both nodes, we swap their values. This approach requires a complete traversal of the list during each pass, but is simple to implement.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def swapNodes(self, head: ListNode, k: int) -> ListNode:
length = 0
first = head
second = head
current = head
while current:
length += 1
if length == k:
first = current
current = current.next
current = head
for i in range(length - k):
current = current.next
second = current
first.val, second.val = second.val, first.val
return headclass ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public class Solution {
public ListNode swapNodes(ListNode head, int k) {
int length = 0;
ListNode first = head;
ListNode second = head;
ListNode current = head;
while (current != null) {
length++;
if (length == k) {
first = current;
}
current = current.next;
}
current = head;
for (int i = 0; i < length - k; i++) {
current = current.next;
}
second = current;
int temp = first.val;
first.val = second.val;
second.val = temp;
return head;
}
}#include <iostream>
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
ListNode* swapNodes(ListNode* head, int k) {
int length = 0;
ListNode* first = head;
ListNode* second = head;
ListNode* current = head;
for (; current != nullptr; current = current->next) {
length++;
if (length == k) {
first = current;
}
}
current = head;
for (int i = 0; i < length - k; i++) {
current = current->next;
}
second = current;
std::swap(first->val, second->val);
return head;
}function ListNode(val, next) {
this.val = (val === undefined ? 0 : val)
this.next = (next === undefined ? null : next)
}
var swapNodes = function(head, k) {
let length = 0;
let first = head, second = head, current = head;
while (current !== null) {
length++;
if (length === k) {
first = current;
}
current = current.next;
}
current = head;
for (let i = 0; i < length - k; i++) {
current = current.next;
}
second = current;
[first.val, second.val] = [second.val, first.val];
return head;
};#include <stdio.h>
#include <stdlib.h>
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* swapNodes(struct ListNode* head, int k) {
int length = 0;
struct ListNode* first = head;
struct ListNode* second = head;
struct ListNode* current = head;
// First pass to compute the length and locate the kth node from the start
for (; current != NULL; current = current->next) {
length++;
if (length == k) {
first = current;
}
}
// Second pass to locate the kth node from the end
current = head;
for (int i = 0; i < length - k; i++) {
current = current->next;
}
second = current;
// Swap the values
int temp = first->val;
first->val = second->val;
second->val = temp;
return head;
}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) {
int length = 0;
ListNode first = head, second = head, current = head;
while (current != null) {
length++;
if (length == k) {
first = current;
}
current = current.next;
}
current = head;
for (int i = 0; i < length - k; i++) {
current = current.next;
}
second = current;
int temp = first.val;
first.val = second.val;
second.val = temp;
return head;
}
}In Python, we create a ListNode class to define nodes of the list. We use a similar technique by traversing through the linked list twice. In the first pass, we ascertain the kth node from the start and the length of the list. In the second pass, we find the kth node from the end, and then swap values.
Time Complexity: O(n). Space Complexity: O(1).
Approach 2: Approach 2: Single Pass with Two Pointers
This approach optimizes the two-pass technique by using a single traversal with two pointers method. The idea is to leverage two pointers where one pointer reaches the kth node while the other starts marking the start from the head. Once the first pointer reaches the end, the second pointer will be at the correct kth position from the end. We then swap the values directly.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def swapNodes(self, head: ListNode, k: int) -> ListNode:
fast = head
slow = head
first = head
for _ in range(k - 1):
fast = fast.next
first = fast
while fast.next:
fast = fast.next
slow = slow.next
first.val, slow.val = slow.val, first.val
return headclass ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public class Solution {
public ListNode swapNodes(ListNode head, int k) {
ListNode fast = head;
ListNode slow = head;
ListNode first = head;
for (int i = 1; i < k; i++) {
fast = fast.next;
}
first = fast;
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
int temp = first.val;
first.val = slow.val;
slow.val = temp;
return head;
}
}#include <iostream>
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
ListNode* swapNodes(ListNode* head, int k) {
ListNode* fast = head;
ListNode* slow = head;
ListNode* first = head;
for (int i = 1; i < k; i++) {
fast = fast->next;
}
first = fast;
while (fast->next != nullptr) {
fast = fast->next;
slow = slow->next;
}
std::swap(first->val, slow->val);
return head;
}function ListNode(val, next) {
this.val = (val === undefined ? 0 : val)
this.next = (next === undefined ? null : next)
}
var swapNodes = function(head, k) {
let fast = head;
let slow = head;
let first = head;
for (let i = 1; i < k; i++) {
fast = fast.next;
}
first = fast;
while (fast.next !== null) {
fast = fast.next;
slow = slow.next;
}
[first.val, slow.val] = [slow.val, first.val];
return head;
};#include <stdio.h>
#include <stdlib.h>
struct ListNode {
int val;
struct ListNode* next;
};
struct ListNode* swapNodes(struct ListNode* head, int k) {
struct ListNode* fast = head;
struct ListNode* slow = head;
struct ListNode* first = head;
struct ListNode* second = head;
// Move fast to the kth node
for (int i = 1; i < k; i++) {
fast = fast->next;
}
first = fast;
// Move both fast and slow such that fast reaches last node
while (fast->next != NULL) {
fast = fast->next;
slow = slow->next;
}
second = slow;
// Swap values
int temp = first->val;
first->val = second->val;
second->val = temp;
return head;
}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, slow = head, first = head;
for (int i = 1; i < k; i++) {
fast = fast.next;
}
first = fast;
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
int temp = first.val;
first.val = slow.val;
slow.val = temp;
return head;
}
}This Python solution succinctly utilizes the fast and slow pointer technique where fast traverses k steps initially and subsequently the full length thereafter, allowing the slow pointer to point accurately to the desired kth node from the end. The swapping is directly implemented using Python's native value assignment.
Time Complexity: O(n). Space Complexity: O(1).
Approach 3: Two Pointers
We can first use a fast pointer fast to find the kth node of the linked list, and use a pointer p to point to it. Then, we use a slow pointer slow to start from the head node of the linked list, and move both pointers forward at the same time. When the fast pointer reaches the last node of the linked list, the slow pointer slow points to the kth node from the end of the linked list, and we use a pointer q to point to it. At this point, we only need to swap the values of p and q.
The time complexity is O(n), where n is the length of the linked list. The space complexity is O(1).
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function swapNodes(head: ListNode | null, k: number): ListNode | null {
let [fast, slow] = [head, head];
while (--k) {
fast = fast.next;
}
const p = fast;
while (fast.next) {
fast = fast.next;
slow = slow.next;
}
const q = slow;
[p.val, q.val] = [q.val, p.val];
return head;
}/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func swapNodes(head *ListNode, k int) *ListNode {
fast := head
for ; k > 1; k-- {
fast = fast.Next
}
p := fast
slow := head
for fast.Next != nil {
fast, slow = fast.Next, slow.Next
}
q := slow
p.Val, q.Val = q.Val, p.Val
return head
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Two Pass Technique | Time Complexity: O(n). Space Complexity: O(1). |
| Approach 2: Single Pass with Two Pointers | Time Complexity: O(n). Space Complexity: O(1). |
| Two Pointers | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two Pass Technique | O(n) | O(1) | When you prefer simpler logic by first computing the list length before locating nodes. |
| Single Pass with Two Pointers | O(n) | O(1) | Best for interviews and optimal implementations where both nodes are found during a single traversal. |
Frequently asked questions
Is Swapping Nodes in a Linked List easy or hard?
This problem is typically classified as Medium difficulty. The challenge comes from correctly locating the kth node from the end without extra memory. Understanding linked list traversal and the two-pointer technique makes the solution straightforward.
Swapping Nodes in a Linked List Python/Java solution
Most implementations keep two node references and swap their values. The logic is identical across languages like Python, Java, C++, and JavaScript: traverse to the kth node, locate the kth node from the end using two pointers, then exchange their values in O(1) space.
How to solve Swapping Nodes in a Linked List in O(n)?
Traverse the list until the kth node from the start is reached and store that reference. Continue traversing while moving another pointer from the head at the same time. When the traversal pointer reaches the last node, the second pointer will point to the kth node from the end. Swap the node values to finish the operation in O(n) time.
What is the best approach for Swapping Nodes in a Linked List?
The single-pass two pointers approach is the most efficient and commonly expected solution. You locate the kth node from the start, then move another pointer from the head while continuing the traversal. When the first pointer reaches the end, the second pointer lands on the kth node from the end. This method runs in O(n) time with O(1) extra space.
Is Swapping Nodes in a Linked List asked at Google/Amazon/Meta?
Linked list pointer manipulation problems like this frequently appear in interviews at companies such as Amazon, Google, and Meta. Variations often test two-pointer techniques, node traversal, and edge cases involving head or tail nodes.
What data structure is used in Swapping Nodes in a Linked List?
The problem operates on a singly linked list. The main techniques involve pointer traversal and the two-pointer pattern to locate nodes efficiently without converting the list into another data structure.
What is the time complexity of Swapping Nodes in a Linked List?
Both common approaches run in O(n) time where n is the number of nodes in the list. The two-pass solution performs two linear traversals, while the optimized two-pointer method completes the task in a single traversal. Each approach uses O(1) extra space since only a few pointer variables are required.