Language Selection
Choose your preferred programming language
Showing: Python
Problem Statement
Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list’s nodes (i.e., only nodes themselves may be changed.)
Input/Output Specifications
- Input: Head of a linked list
- Output: Head of the linked list with adjacent nodes swapped
- Constraints:
- The number of nodes in the list is in the range [0, 100]
- 0 <= Node.val <= 100
Examples
Example 1:
Input: head = [1,2,3,4]
Output: [2,1,4,3]
Example 2:
Input: head = []
Output: []
Example 3:
Input: head = [1]
Output: [1]
Solutions
Approach 1: Iterative (Three Pointers)
This approach uses three pointers to swap adjacent nodes iteratively.
Algorithm:
- Create a dummy head to simplify edge cases
- Use three pointers: prev, first, and second
- While we have at least two nodes to swap:
- Update pointers to perform the swap
- Move prev to the new position
- Return the head (skip dummy)
Python:
def swapPairs(head):
"""
Swap every two adjacent nodes iteratively
Time: O(n)
Space: O(1)
"""
dummy = ListNode(0)
dummy.next = head
prev = dummy
while prev.next and prev.next.next:
first = prev.next
second = prev.next.next
# Perform the swap
prev.next = second
first.next = second.next
second.next = first
# Move prev to the new position
prev = first
return dummy.next
Java:
class Solution {
/**
* Swap every two adjacent nodes iteratively
* Time: O(n)
* Space: O(1)
*/
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy;
while (prev.next != null && prev.next.next != null) {
ListNode first = prev.next;
ListNode second = prev.next.next;
// Perform the swap
prev.next = second;
first.next = second.next;
second.next = first;
// Move prev to the new position
prev = first;
}
return dummy.next;
}
}
Go:
// swapPairs - Swap every two adjacent nodes iteratively
// Time: O(n)
// Space: O(1)
func swapPairs(head *ListNode) *ListNode {
dummy := &ListNode{Val: 0, Next: head}
prev := dummy
for prev.Next != nil && prev.Next.Next != nil {
first := prev.Next
second := prev.Next.Next
// Perform the swap
prev.Next = second
first.Next = second.Next
second.Next = first
// Move prev to the new position
prev = first
}
return dummy.Next
}
JavaScript:
/**
* Swap every two adjacent nodes iteratively
* Time: O(n)
* Space: O(1)
*/
function swapPairs(head) {
const dummy = new ListNode(0);
dummy.next = head;
let prev = dummy;
while (prev.next !== null && prev.next.next !== null) {
const first = prev.next;
const second = prev.next.next;
// Perform the swap
prev.next = second;
first.next = second.next;
second.next = first;
// Move prev to the new position
prev = first;
}
return dummy.next;
}
C#:
public class Solution {
/// <summary>
/// Swap every two adjacent nodes iteratively
/// Time: O(n)
/// Space: O(1)
/// </summary>
public ListNode SwapPairs(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy;
while (prev.next != null && prev.next.next != null) {
ListNode first = prev.next;
ListNode second = prev.next.next;
// Perform the swap
prev.next = second;
first.next = second.next;
second.next = first;
// Move prev to the new position
prev = first;
}
return dummy.next;
}
}
Approach 2: Recursive Solution
This approach uses recursion to swap pairs by handling the first two nodes and recursively processing the rest.
Algorithm:
- Base case: if head is null or head.next is null, return head
- Store the second node as the new head
- Recursively swap the rest of the list
- Connect the swapped rest to the first node
- Return the new head (second node)
Python:
def swapPairsRecursive(head):
"""
Swap every two adjacent nodes recursively
Time: O(n)
Space: O(n) - due to recursion stack
"""
if not head or not head.next:
return head
# Store the second node as the new head
new_head = head.next
# Recursively swap the rest
head.next = swapPairsRecursive(head.next.next)
# Connect the swapped rest to the first node
new_head.next = head
return new_head
Java:
class Solution {
/**
* Swap every two adjacent nodes recursively
* Time: O(n)
* Space: O(n) - due to recursion stack
*/
public ListNode swapPairsRecursive(ListNode head) {
if (head == null || head.next == null) {
return head;
}
// Store the second node as the new head
ListNode newHead = head.next;
// Recursively swap the rest
head.next = swapPairsRecursive(head.next.next);
// Connect the swapped rest to the first node
newHead.next = head;
return newHead;
}
}
Go:
// swapPairsRecursive - Swap every two adjacent nodes recursively
// Time: O(n)
// Space: O(n) - due to recursion stack
func swapPairsRecursive(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
// Store the second node as the new head
newHead := head.Next
// Recursively swap the rest
head.Next = swapPairsRecursive(head.Next.Next)
// Connect the swapped rest to the first node
newHead.Next = head
return newHead
}
JavaScript:
/**
* Swap every two adjacent nodes recursively
* Time: O(n)
* Space: O(n) - due to recursion stack
*/
function swapPairsRecursive(head) {
if (head === null || head.next === null) {
return head;
}
// Store the second node as the new head
const newHead = head.next;
// Recursively swap the rest
head.next = swapPairsRecursive(head.next.next);
// Connect the swapped rest to the first node
newHead.next = head;
return newHead;
}
C#:
public class Solution {
/// <summary>
/// Swap every two adjacent nodes recursively
/// Time: O(n)
/// Space: O(n) - due to recursion stack
/// </summary>
public ListNode SwapPairsRecursive(ListNode head) {
if (head == null || head.next == null) {
return head;
}
// Store the second node as the new head
ListNode newHead = head.next;
// Recursively swap the rest
head.next = SwapPairsRecursive(head.next.next);
// Connect the swapped rest to the first node
newHead.next = head;
return newHead;
}
}
Key Insights
- Three-pointer technique: Use prev, first, and second pointers for iterative swapping
- Dummy node: Simplifies edge cases and pointer management
- Pointer order: Careful ordering of pointer updates prevents losing references
- Recursive pattern: Handle first pair, then recursively process the rest
- Edge case handling: Handle odd-length lists and single nodes properly
Edge Cases
- Empty list
- Single node list
- Two node list
- Odd number of nodes
- Even number of nodes
Test Cases
# Test case 1: Even number of nodes
head1 = ListNode(1)
head1.next = ListNode(2)
head1.next.next = ListNode(3)
head1.next.next.next = ListNode(4)
# Expected: [2,1,4,3]
# Test case 2: Odd number of nodes
head2 = ListNode(1)
head2.next = ListNode(2)
head2.next.next = ListNode(3)
# Expected: [2,1,3]
# Test case 3: Two nodes
head3 = ListNode(1)
head3.next = ListNode(2)
# Expected: [2,1]
# Test case 4: Single node
head4 = ListNode(1)
# Expected: [1]
# Test case 5: Empty list
head5 = None
# Expected: []
Follow-up Questions
- How would you swap every k nodes instead of every 2?
- Can you solve this without using a dummy node?
- How would you handle very large lists?
- What if you need to swap nodes in groups of 3?
Common Mistakes
- Not handling empty lists and single nodes
- Incorrect pointer ordering during swap
- Losing references to nodes during the swap
- Not updating the prev pointer correctly
- Stack overflow in recursive approach for very long lists
- Off-by-one errors in pointer movement