Swap Nodes in Pairs - Practice Coding Problems

Swap Nodes in Pairs - Problem

Given the head of 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).

For example, if the linked list is 1→2→3→4, the result should be 2→1→4→3.

Input & Output

Example 1 — Four Node List

$ Input: [1,2,3,4]

› Output: [2,1,4,3]

💡 Note: Swap pairs (1,2) and (3,4): 1→2→3→4 becomes 2→1→4→3

Example 2 — Odd Length List

$ Input: [1,2,3]

› Output: [2,1,3]

💡 Note: Swap pair (1,2), leave 3 unchanged: 1→2→3 becomes 2→1→3

Example 3 — Empty List

$ Input: []

› Output: []

💡 Note: Empty list remains empty

Constraints

The number of nodes in the list is in the range [0, 100]
0 ≤ Node.val ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input

Original linked list with nodes in sequential order

Process

Swap every two adjacent nodes by updating pointers

Output

Modified list with pairs swapped

Key Takeaway

🎯 Key Insight: Use pointer manipulation to swap adjacent pairs without modifying node values

Asked in

f Facebook 42 M Microsoft 38 a Amazon 35 G Google 28

The key insight is to safely swap adjacent pairs by either using a dummy node for iterative approach or leveraging recursion's natural divide-and-conquer. Best approach is iterative with dummy node for O(1) space. Time: O(n), Space: O(1) for iterative or O(n) for recursive.

Common Approaches

Approach	Time	Space	Notes
✓ Recursive Approach	O(n)	O(n)	Use recursion to swap current pair and recursively handle the rest of the list
Iterative with Dummy Node	O(n)	O(1)	Use a dummy node and iteratively swap adjacent pairs using pointer manipulation

Recursive Approach — Algorithm Steps

Base case: if head is null or only one node, return head
Save reference to the second node
Recursively swap the rest of the list starting from third node
Point first node to the result of recursive call, second node to first node

Visualization

Tap to expand

Step-by-Step Walkthrough

Identify

Take first two nodes as current pair

Recurse

Recursively swap remaining nodes starting from third

Connect

Connect swapped pair with recursively processed rest

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct ListNode {
    int val;
    struct ListNode* next;
};

struct ListNode* solution(struct ListNode* head) {
    if (!head || !head->next) {
        return head;
    }
    
    struct ListNode* second = head->next;
    head->next = solution(second->next);
    second->next = head;
    
    return second;
}

struct ListNode* arrayToList(int* arr, int size) {
    if (size == 0) return NULL;
    struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->val = arr[0];
    head->next = NULL;
    struct ListNode* current = head;
    for (int i = 1; i < size; i++) {
        current->next = (struct ListNode*)malloc(sizeof(struct ListNode));
        current = current->next;
        current->val = arr[i];
        current->next = NULL;
    }
    return head;
}

int* listToArray(struct ListNode* head, int* size) {
    *size = 0;
    struct ListNode* current = head;
    while (current) {
        (*size)++;
        current = current->next;
    }
    
    int* result = (int*)malloc(*size * sizeof(int));
    current = head;
    for (int i = 0; i < *size; i++) {
        result[i] = current->val;
        current = current->next;
    }
    return result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    int arr[100];
    int size = 0;
    char* token = strtok(line + 1, ",]");
    while (token) {
        arr[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    struct ListNode* head = arrayToList(arr, size);
    struct ListNode* result = solution(head);
    
    int resultSize;
    int* resultArr = listToArray(result, &resultSize);
    
    printf("[");
    for (int i = 0; i < resultSize; i++) {
        printf("%d", resultArr[i]);
        if (i < resultSize - 1) printf(",");
    }
    printf("]\n");
    
    free(resultArr);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Visit each node exactly once during recursion

✓ Linear Growth

Space Complexity

O(n)

Recursion stack depth is n/2 for the recursive calls

⚡ Linearithmic Space

425.0K Views

High Frequency

~15 min Avg. Time

9.0K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Recursive Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler