Swap Nodes in Pairs - Java Solution

1. Introduction

This blog post focuses on solving the "Swap Nodes in Pairs" problem, a common task in linked list manipulation. The challenge involves swapping every two adjacent nodes in a linked list, a problem that tests one's understanding of linked list traversal and node manipulation without altering the node values.

Problem

Given a linked list, the task is to swap every two adjacent nodes and return the head of the modified list. The key requirement is to perform the swap by changing the node links, without modifying the values stored in the nodes.

2. Solution Steps

1. Create a dummy head node to simplify edge case handling.

2. Initialize a pointer current to point to the dummy head.

3. Iterate through the list while there are at least two nodes remaining for swapping.

4. For each pair:

a. Point current.next to the second node of the pair.

b. Adjust the first node of the pair to point to the third node (or null if it's the end of the list).

c. Update current to the first node of the pair (which is now the second node after swapping).

5. Return the next node of the dummy head as the new head of the list.

3. Code Program

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

public class SwapNodesInPairs {
    public static void main(String[] args) {
        // Example use case
        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;
        }
    }

    // Function to swap nodes in pairs
    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 firstNode = current.next;
            ListNode secondNode = current.next.next;

            // Swap the nodes
            firstNode.next = secondNode.next;
            secondNode.next = firstNode;
            current.next = secondNode;

            // Move to the next pair
            current = firstNode;
        }

        return dummy.next;
    }
}

Output:

2 1 4 3

Explanation:

1. swapPairs: This function swaps every two adjacent nodes in the linked list.

2. A dummy node is used at the start of the list to handle edge cases, especially when swapping the first pair of nodes.

3. The function iterates through the list, swapping pairs of nodes by adjusting their next pointers.

4. After swapping a pair, it moves current to the end of the swapped pair to prepare for the next swap.

5. The swapping of nodes is done by changing pointers, not node values, adhering to the problem's requirement.

6. Finally, the function returns the head of the modified list, which is the next node after the dummy node.

7. This approach efficiently swaps the nodes in pairs with a single traversal of the list and without modifying the node values.