AlgoBreath

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

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

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

  3. 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:

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

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

Next