Given the head of a singly linked list, swap every two adjacent nodes and return the modified head. Node values must stay inside the original nodes, so the task swaps node links instead of rewriting values.
When the linked list contains an odd number of nodes, the last node remains in the same position because no partner node exists for the final swap.
Example 1
Input: head = [1, 2, 3, 4]
Output: [2, 1, 4, 3]
Explanation: Pair (1, 2) becomes (2, 1) and pair (3, 4) becomes (4, 3).
Example 2
Input: head = [1, 2, 3]
Output: [2, 1, 3]
Explanation: Last node remains unchanged because no second node is available for the final pair.
Brute Force Approach
A beginner-friendly way to view the task is to read the linked list into an array, swap values inside the array pair by pair, and then write the swapped values back into the linked list. The linked-list shape stays unchanged, so the main work happens through array storage and array-based pair movement.
Algorithm
Initialize an array to store the linked-list values, as using an array makes adjacent elements easy to access and swap.
Traverse the linked list once and push every node value into the array, so the values are available by index without changing the linked-list structure.
Traverse the array with a step of two, as each iteration represents one pair of adjacent nodes.
Swap the two values when a complete pair exists, since swapping each pair of adjacent values produces the required pairwise reversal.
Reset a traversal pointer to
head, as the modified array values now need to be written back into the original nodes.Traverse the linked list again and overwrite each node's value with the corresponding value from the modified array, which transfers the pairwise-swapped order back to the list.
Return the original
head, as the linked-list connections remain unchanged and only the node values have been rearranged.
Dry Run
swap nodes array rewrite
Solution
#include <bits/stdc++.h>using namespace std;struct ListNode { int data; Node* next; ListNode(int value) { data = value; next = nullptr; }};class Solution {public: // Swap adjacent nodes by collecting values ListNode* swapPairs(ListNode* head) { // Return early for empty or single-node lists. if (head == nullptr || head->next == nullptr) { return head; } // Store all node values in encounter order. vector<int> values; // Traverse the list and collect values. ListNode* current = head; while (current != nullptr) { values.push_back(current->data); current = current->next; } // Swap adjacent values inside the array. for (int i = 0; i + 1 < (int)values.size(); i += 2) { swap(values[i], values[i + 1]); } // Reset traversal for value rewriting. current = head; int index = 0; // Write swapped values back into the linked list. while (current != nullptr) { current->data = values[index++]; current = current->next; } // Return the updated head. return head; }};// Build a linked list from an array.ListNode* buildList(const vector<int>& values) { ListNode* dummy = new ListNode(0); ListNode* tail = dummy; for (int value : values) { tail->next = new ListNode(value); tail = tail->next; } return dummy->next;}// Print the linked list in one line.void printList(ListNode* head) { while (head != nullptr) { cout << head->data; if (head->next != nullptr) { cout << " "; } head = head->next; } cout << "\n";}// Run the array-based solution on a hard-coded sample.int main() { vector<int> values = {1, 2, 3, 4}; ListNode* head = buildList(values); Solution solution; ListNode* answer = solution.swapPairs(head); printList(answer); return 0;}Complexity Analysis
Time Complexity: O(N), one traversal collects values, one array loop swaps pairs, and one traversal rewrites values.
Space Complexity: O(N), extra array storage holds all node values.
Optimal Approach
The strongest linked-list solution swaps nodes directly by changing next pointers around each adjacent pair. A dummy node before the head removes special handling for the first pair, and one straight traversal keeps jumping pair by pair across the chain.
Algorithm
Initialize a dummy node and link it to the original
head, as the dummy node provides a node before the first pair and keeps the first swap consistent with all other pairs.Initialize a pointer
prevat the dummy node, whereprevrepresents the node immediately before the pair currently being processed.Traverse while two nodes are available for the next swap, since a pairwise swap is possible only when both nodes exist.
Store the first node, second node, and the node after the pair, as these references are needed to reconnect the three parts without losing the remaining list.
Link
prevto the second node and the second node to the first node, which reverses the order of the current pair.Link the first node to the node after the pair, preserving the connection with the remaining linked list.
Move
prevto the first node, as it becomes the last node of the newly swapped pair and therefore the node immediately before the next pair.Continue the same process for every available pair and return
dummy.nextas the new head, since the dummy node itself is not part of the final linked list.
Dry Run
swap pairs optimal
Solution
#include <bits/stdc++.h>using namespace std;class ListNode {public: int val; ListNode* next; ListNode(int data) { val = data; next = nullptr; }};class Solution {public: // Swap adjacent nodes in place by relinking pointers pair by pair. ListNode* swapPairs(ListNode* head) { // Dummy node simplifies swapping of the first pair. ListNode* dummy = new ListNode(0); dummy->next = head; // Previous pointer stays just before the current pair. ListNode* prev = dummy; // Continue while a complete pair is available. while (prev->next != nullptr && prev->next->next != nullptr) { // First node of the current pair. ListNode* first = prev->next; // Second node of the current pair. ListNode* second = first->next; // First node after the current pair. ListNode* nextPair = second->next; // Place the second node before the first node. prev->next = second; // Place the first node after the second node. second->next = first; // Reconnect the swapped pair with the remaining list. first->next = nextPair; // Move previous pointer to the end of the swapped pair. prev = first; } // Return the real head after skipping the dummy node. return dummy->next; }};// Build a linked list from an array.ListNode* buildList(const vector<int>& values) { ListNode* dummy = new ListNode(0); ListNode* tail = dummy; for (int value : values) { tail->next = new ListNode(value); tail = tail->next; } return dummy->next;}// Print the linked list in one line.void printList(ListNode* head) { while (head != nullptr) { cout << head->val; if (head->next != nullptr) { cout << " "; } head = head->next; } cout << "\n";}// Run the in-place solution on a hard-coded sample.int main() { vector<int> values = {1, 2, 3, 4}; ListNode* head = buildList(values); Solution solution; ListNode* answer = solution.swapPairs(head); printList(answer); return 0;}Complexity Analysis
Time Complexity: O(N), each node participates in one constant-time pointer update sequence.
Space Complexity: O(1), only a fixed number of pointer variables and one dummy node are used.
Interview follow-up Questions
The optimal solution swaps the links between adjacent nodes while keeping the values inside the original nodes unchanged.
Be the first to add a comment.