Swap Nodes in Pairs - Python Solution

1. Introduction

"Swap Nodes in Pairs" is an engaging problem that deals with linked list manipulation. It challenges one to swap adjacent nodes in a linked list, a common task in various applications of linked lists. This problem tests the understanding of linked list traversal and node manipulation without altering the actual node data.

Problem

Given a linked list, the task is to swap every two adjacent nodes and return the head of the modified list. The problem requires solving without changing the values in the list's nodes, meaning only the nodes themselves may be rearranged.

2. Solution Steps

1. Create a dummy node and point its next to the head of the list. This dummy node simplifies edge cases.

2. Initialize two pointers, prev and current, where prev is the dummy node and current is the head of the list.

3. Traverse the list while current and current.next are not null.

4. Swap the nodes by adjusting the pointers: prev.next points to current.next, current.next points to current.next.next, and prev.next.next points to current.

5. Move prev and current forward by two nodes each for the next pair.

6. Continue this process until the end of the list is reached.

7. Return the next node of the dummy node, which is the new head of the list.

3. Code Program

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

def swapPairs(head):
    dummy = ListNode(0)
    dummy.next = head
    prev, current = dummy, head

    while current and current.next:
        # Swapping nodes
        next_pair = current.next.next
        second = current.next

        second.next = current
        current.next = next_pair
        prev.next = second

        # Moving to the next pair
        prev = current
        current = next_pair

    return dummy.next

# Example Usage
# Creating list for demonstration: [1 -> 2 -> 3 -> 4]
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4))))
result = swapPairs(head)
# Output the list
output = []
while result:
    output.append(result.val)
    result = result.next
print(output)

Output:

[2, 1, 4, 3]

Explanation:

1. ListNode Class: The ListNode class represents each node in the linked list.

2. Dummy Node: A dummy node is used to simplify the swapping logic at the start of the list.

3. Swapping Logic: Adjacent nodes are swapped by carefully adjusting their next pointers.

4. Pointer Movement: After swapping a pair, the pointers are updated to the next pair of nodes.

5. Traversing the List: The list is traversed in pairs, swapping each pair in turn.

6. Returning Result: The node next to the dummy node becomes the head of the swapped list.

7. In-place Swapping: The approach swaps nodes without altering the node values, adhering to the problem constraints.