Swap Nodes in Pairs Problem and Solution

1. Introduction

A comprehensive guide to solving the "Swap Nodes in Pairs" problem in multiple programming languages (C++, Java, and Python), including detailed explanations and outputs.

The "Swap Nodes in Pairs" problem involves swapping every two adjacent nodes of a linked list and returning its head. It's a problem that tests understanding of linked list manipulation.

2. Problem

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).

3. Solution in C++

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* swapPairs(ListNode* head) {
    ListNode *dummy = new ListNode(0);
    dummy->next = head;
    ListNode *current = dummy;
    while (current->next != nullptr && current->next->next != nullptr) {
        ListNode *first = current->next;
        ListNode *second = current->next->next;
        first->next = second->next;
        current->next = second;
        second->next = first;
        current = first;
    }
    ListNode *result = dummy->next;
    delete dummy;
    return result;
}

// Example usage
int main() {
    ListNode *head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    ListNode *result = swapPairs(head);
    while (result != nullptr) {
        cout << result->val << " ";
        result = result->next;
    }
    return 0;
}

Output:

2 1 4 3

Explanation:

1. swapPairs in C++ uses a dummy node to simplify edge cases.

2. It iterates through the list, swapping pairs of nodes by adjusting pointers.

3. Continues until no more pairs are left to swap.

4. Returns the head of the modified list after removing the dummy node.

4. Solution in Java

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }

    public static ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode current = dummy;
        while (current.next != null && current.next.next != null) {
            ListNode first = current.next;
            ListNode second = current.next.next;
            first.next = second.next;
            current.next = second;
            second.next = first;
            current = first;
        }
        return dummy.next;
    }

    // Example usage
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        ListNode result = swapPairs(head);
        while (result != null) {
            System.out.print(result.val + " ");
            result = result.next;
        }
    }
}

Output:

2 1 4 3

Explanation:

1. Java's swapPairs method also uses a dummy node.

2. Iterates through the list, swapping adjacent nodes by reassigning their next pointers.

3. Proceeds until all pairs are swapped.

4. Returns the new head of the list after discarding the dummy node.

5. Solution in Python

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def swap_pairs(head):
    dummy = ListNode(0, head)
    prev, current = dummy, head

    while current and current.next:
        first = current
        second = current.next

        prev.next = second
        first.next = second.next
        second.next = first

        prev = first
        current = first.next

    return dummy.next

# Example usage
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4))))
result = swap_pairs(head)
while result:
    print(result.val, end=" ")
    result = result.next

Output:

2 1 4 3

Explanation:

1. Python's swap_pairs function uses a dummy node.

2. It iterates through the list, swapping adjacent nodes.

3. Adjusts the next pointers to swap the nodes and progresses through the list.

4. Returns the new head of the list after the dummy node.