Swap Nodes in Pairs

"Swap Nodes in Pairs" is a problem typically found in the context of data structures, specifically linked lists. To explain this, let's start with the basics.

Fundamental Concepts

Linked List: A linked list is a linear data structure where each element (node) contains a value and a reference (or link) to the next node in the sequence. Unlike arrays, nodes in a linked list are not stored at contiguous memory locations; they are linked using pointers.
Node: Each element in a linked list is called a node. A typical node has two parts: data (value) and a pointer (reference to the next node).
Swapping Nodes: Swapping nodes involves changing the links or pointers so that the order of nodes is reversed for the pair. It doesn't involve swapping data between nodes.

Problem Statement: Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head. For example, if the linked list is 1->2->3->4, the result after swapping in pairs should be 2->1->4->3.

Approach to Solve

To solve this problem:

Iterative Approach:
- Traverse the linked list in pairs.
- For each pair, adjust the pointers to swap the nodes.
- Handle the end of the list carefully (if it has an odd number of nodes).
Recursive Approach:
- Swap the first two nodes.
- Recursively call the function for the rest of the list.
- Link the returned head of the sub-list to the second node of the current pair.

Example: Iterative Approach

Let's assume a basic node structure:

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

Here is how you might implement the swap:

def swapPairs(head):
    # A dummy node to simplify edge cases like empty list or a list with single node
    dummy = ListNode(0)
    dummy.next = head

    # Initialize the current node to start from dummy
    current = dummy

    while current.next and current.next.next:
        # Nodes to be swapped
        first = current.next
        second = current.next.next

        # Swapping
        first.next = second.next
        second.next = first
        current.next = second

        # Move to the next pair
        current = current.next.next

    # Return the new head of the list
    return dummy.next

In this code:

dummy node is a placeholder to handle edge cases.
We iterate through the list in pairs (while current.next and current.next.next).
first and second are the two nodes in the current pair.
We adjust next pointers to swap first and second.
After swapping, we move current to the next pair.

This approach ensures that all pairs are swapped, handling both even and odd-length lists gracefully. The use of a dummy node simplifies edge cases, making the code more robust and easier to understand.

Prev Next