.png)
Swap Nodes in Pairs
Problem
Given the head of a Singly Linked List, swap every two adjacent nodes and return the modified head.
You must swap nodes, not just their data.
If the number of nodes is odd, the last node remains unchanged.
Example
Input
1 → 2 → 3 → 4 → 5
Output
2 → 1 → 4 → 3 → 5
Approach 1 — Iterative Pointer Manipulation
Idea
Swap nodes in pairs by adjusting links while traversing the list.
Use a dummy node to simplify handling of the head.
Steps
- Create a dummy node pointing to head
- Use a pointer prev initially at dummy
- While two nodes exist:
- Let first = prev.next
- Let second = first.next
- Perform swapping:
- first.next = second.next
- second.next = first
- prev.next = second
- Move prev = first
- Continue until pairs end
- Return dummy.next
Time Complexity
O(N)
Space Complexity
O(1)
Input
1 → 2 → 3 → 4 → 5
Output
2 → 1 → 4 → 3 → 5
C Implementation
// While running this code, replace all #include "..." with #include <...>
#include "stdio.h"
#include "stdlib.h"
struct Node {
int data;
struct Node* next;
};
struct Node* swapPairs(struct Node* head) {
struct Node dummy;
dummy.next = head;
struct Node* prev = &dummy;
while (prev->next && prev->next->next) {
struct Node* first = prev->next;
struct Node* second = first->next;
// Swapping
first->next = second->next;
second->next = first;
prev->next = second;
prev = first;
}
return dummy.next;
}
void printList(struct Node* head) {
while (head) {
printf("%d ", head->data);
head = head->next;
}
}
int main() {
// 1 → 2 → 3 → 4 → 5
struct Node* head = (struct Node*)malloc(sizeof(struct Node));
head->data = 1;
head->next = (struct Node*)malloc(sizeof(struct Node));
head->next->data = 2;
head->next->next = (struct Node*)malloc(sizeof(struct Node));
head->next->next->data = 3;
head->next->next->next = (struct Node*)malloc(sizeof(struct Node));
head->next->next->next->data = 4;
head->next->next->next->next = (struct Node*)malloc(sizeof(struct Node));
head->next->next->next->next->data = 5;
head->next->next->next->next->next = NULL;
head = swapPairs(head);
printList(head);
return 0;
}Output
2 1 4 3 5
C++ Implementation
// While running this code, replace all #include "..." with #include <...>
#include "iostream"
using namespace std;
class Node {
public:
int data;
Node* next;
Node(int x) {
data = x;
next = NULL;
}
};
Node* swapPairs(Node* head) {
Node dummy(0);
dummy.next = head;
Node* prev = &dummy;
while (prev->next && prev->next->next) {
Node* first = prev->next;
Node* second = first->next;
// Swapping
first->next = second->next;
second->next = first;
prev->next = second;
prev = first;
}
return dummy.next;
}
void printList(Node* head) {
while (head) {
cout << head->data << " ";
head = head->next;
}
}
int main() {
Node* head = new Node(1);
head->next = new Node(2);
head->next->next = new Node(3);
head->next->next->next = new Node(4);
head->next->next->next->next = new Node(5);
head = swapPairs(head);
printList(head);
return 0;
}Output
2 1 4 3 5
Java Implementation
class Node {
int data;
Node next;
Node(int d) {
data = d;
next = null;
}
}
public class Main {
static Node swapPairs(Node head) {
Node dummy = new Node(0);
dummy.next = head;
Node prev = dummy;
while (prev.next != null && prev.next.next != null) {
Node first = prev.next;
Node second = first.next;
first.next = second.next;
second.next = first;
prev.next = second;
prev = first;
}
return dummy.next;
}
static void printList(Node head) {
while (head != null) {
System.out.print(head.data + " ");
head = head.next;
}
}
public static void main(String[] args) {
Node head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
head.next.next.next = new Node(4);
head.next.next.next.next = new Node(5);
head = swapPairs(head);
printList(head);
}
}
Output
2 1 4 3 5
Python Implementation
class Node:
def __init__(self, data):
self.data = data
self.next = None
def swap_pairs(head):
dummy = Node(0)
dummy.next = head
prev = dummy
while prev.next and prev.next.next:
first = prev.next
second = first.next
first.next = second.next
second.next = first
prev.next = second
prev = first
return dummy.next
def print_list(head):
while head:
print(head.data, end=" ")
head = head.next
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(4)
head.next.next.next.next = Node(5)
head = swap_pairs(head)
print_list(head)
Output
2 1 4 3 5
JavaScript Implementation
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
function swapPairs(head) {
let dummy = new Node(0);
dummy.next = head;
let prev = dummy;
while (prev.next && prev.next.next) {
let first = prev.next;
let second = first.next;
first.next = second.next;
second.next = first;
prev.next = second;
prev = first;
}
return dummy.next;
}
function printList(head) {
while (head !== null) {
process.stdout.write(head.data + " ");
head = head.next;
}
}
let head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
head.next.next.next = new Node(4);
head.next.next.next.next = new Node(5);
head = swapPairs(head);
printList(head);
Output
2 1 4 3 5
Approach 2 — Recursive Swapping
Idea
In this approach, we swap nodes in pairs using recursion.
At each recursive step:
- Swap the first two nodes
- Recursively swap the remaining list
- Connect the swapped pair with the result of recursion
Steps
- Base Case
- If head is NULL OR head.next is NULL
→ return head (no pair to swap)
- If head is NULL OR head.next is NULL
- Identify nodes
- first = head
- second = head.next
- Recursively swap remaining list starting from second.next
- Adjust links
- first.next = recursiveResult
- second.next = first
- Return second as new head of this pair
Time Complexity
O(N)
Space Complexity
O(N)
(Recursion stack)
Input
1 → 2 → 3 → 4 → 5
Output
2 → 1 → 4 → 3 → 5
C Implementation
// While running this code, replace all #include "..." with #include <...>
#include "stdio.h"
#include "stdlib.h" // Corrected
struct Node {
int data;
struct Node* next;
};
struct Node* swapPairs(struct Node* head) {
if (head == NULL || head->next == NULL)
return head;
struct Node* first = head;
struct Node* second = head->next;
// Recursive call
first->next = swapPairs(second->next);
second->next = first;
return second;
}
void printList(struct Node* head) {
while (head) {
printf("%d ", head->data);
head = head->next;
}
}
int main() {
struct Node* head = (struct Node*)malloc(sizeof(struct Node));
head->data = 1;
head->next = (struct Node*)malloc(sizeof(struct Node));
head->next->data = 2;
head->next->next = (struct Node*)malloc(sizeof(struct Node));
head->next->next->data = 3;
head->next->next->next = (struct Node*)malloc(sizeof(struct Node));
head->next->next->next->data = 4;
head->next->next->next->next = (struct Node*)malloc(sizeof(struct Node));
head->next->next->next->next->data = 5;
head->next->next->next->next->next = NULL;
head = swapPairs(head);
printList(head);
return 0;
}Output
2 1 4 3 5
C++ Implementation
// While running this code, replace all #include "..." with #include <...>
#include "iostream"
using namespace std;
class Node {
public:
int data;
Node* next;
Node(int x) {
data = x;
next = NULL;
}
};
Node* swapPairs(Node* head) {
if (head == NULL || head->next == NULL)
return head;
Node* first = head;
Node* second = head->next;
first->next = swapPairs(second->next);
second->next = first;
return second;
}
void printList(Node* head) {
while (head) {
cout << head->data << " ";
head = head->next;
}
}
int main() {
Node* head = new Node(1);
head->next = new Node(2);
head->next->next = new Node(3);
head->next->next->next = new Node(4);
head->next->next->next->next = new Node(5);
head = swapPairs(head);
printList(head);
return 0;
}Output
2 1 4 3 5
Java Implementation
class Node {
int data;
Node next;
Node(int d) {
data = d;
next = null;
}
}
public class Main {
static Node swapPairs(Node head) {
if (head == null || head.next == null)
return head;
Node first = head;
Node second = head.next;
first.next = swapPairs(second.next);
second.next = first;
return second;
}
static void printList(Node head) {
while (head != null) {
System.out.print(head.data + " ");
head = head.next;
}
}
public static void main(String[] args) {
Node head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
head.next.next.next = new Node(4);
head.next.next.next.next = new Node(5);
head = swapPairs(head);
printList(head);
}
}
Output
2 1 4 3 5
Python Implementation
class Node:
def __init__(self, data):
self.data = data
self.next = None
def swap_pairs(head):
if not head or not head.next:
return head
first = head
second = head.next
first.next = swap_pairs(second.next)
second.next = first
return second
def print_list(head):
while head:
print(head.data, end=" ")
head = head.next
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(4)
head.next.next.next.next = Node(5)
head = swap_pairs(head)
print_list(head)
Output
2 1 4 3 5
JavaScript Implementation
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
function swapPairs(head) {
if (head === null || head.next === null)
return head;
let first = head;
let second = head.next;
first.next = swapPairs(second.next);
second.next = first;
return second;
}
function printList(head) {
while (head !== null) {
process.stdout.write(head.data + " ");
head = head.next;
}
}
let head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
head.next.next.next = new Node(4);
head.next.next.next.next = new Node(5);
head = swapPairs(head);
printList(head);
Output
2 1 4 3 5
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.jpg)
.jpg)
.jpg)
.jpg)
