Swap Two Nodes in a Singly Linked List

Swapping Two Nodes

Swapping two nodes in a singly linked list involves changing the links of the nodes to swap their positions without altering the data inside the nodes. This operation requires careful manipulation of pointers to maintain the integrity of the list.

---

Step-by-Step Process

Consider a singly linked list with the following structure before swapping:

Head -> 1 -> 2 -> 3 -> 4 -> 5 -> None

To swap nodes with values 2 and 4, follow these steps:

1. Initialize Pointers: Start with pointers to keep track of the previous and current nodes for both nodes to be swapped.
2. Traverse the List: Find the two nodes to be swapped and their previous nodes.
3. Swap the Nodes: Change the next pointers of the previous nodes and the nodes themselves to swap their positions.

---

Pseudo Code

Function swap_nodes(head, x, y):
    # If x and y are the same, no need to swap
    If x == y:
        Return head
    
    # Initialize pointers for x
    prevX = None
    currX = head
    While currX is not null and currX.data != x:
        prevX = currX
        currX = currX.next
    
    # Initialize pointers for y
    prevY = None
    currY = head
    While currY is not null and currY.data != y:
        prevY = currY
        currY = currY.next
    
    # If either x or y is not present, return the original head
    If currX is null or currY is null:
        Return head
    
    # If x is not the head of the list, update the previous node's next to y
    If prevX is not null:
        prevX.next = currY
    Else:
        head = currY
    
    # If y is not the head of the list, update the previous node's next to x
    If prevY is not null:
        prevY.next = currX
    Else:
        head = currX
    
    # Swap the next pointers of x and y
    temp = currX.next
    currX.next = currY.next
    currY.next = temp
    
    Return head

---

Python Program to Swap Two Nodes in a Singly Linked List

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class SinglyLinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        # Create a new node with the given data
        new_node = Node(data)
        # If the list is empty, set the new node as the head
        if self.head is None:
            self.head = new_node
        else:
            # Traverse to the end of the list and append the new node
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node

    def swap_nodes(self, x, y):
        # If x and y are the same, no need to swap
        if x == y:
            return

        # Initialize pointers for x
        prevX = None
        currX = self.head
        while currX and currX.data != x:
            prevX = currX
            currX = currX.next

        # Initialize pointers for y
        prevY = None
        currY = self.head
        while currY and currY.data != y:
            prevY = currY
            currY = currY.next

        # If either x or y is not present, return
        if not currX or not currY:
            return

        # If x is not the head of the list, update the previous node's next to y
        if prevX:
            prevX.next = currY
        else:
            self.head = currY

        # If y is not the head of the list, update the previous node's next to x
        if prevY:
            prevY.next = currX
        else:
            self.head = currX

        # Swap the next pointers of x and y
        temp = currX.next
        currX.next = currY.next
        currY.next = temp

    def traverse(self):
        # Traverse and print the linked list
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# Example usage:
linked_list = SinglyLinkedList()
linked_list.append(1)
linked_list.append(2)
linked_list.append(3)
linked_list.append(4)
linked_list.append(5)
print("Linked list before swapping 2 and 4:")
linked_list.traverse()  # Output: 1 -> 2 -> 3 -> 4 -> 5 -> None
linked_list.swap_nodes(2, 4)
print("Linked list after swapping 2 and 4:")
linked_list.traverse()  # Output: 1 -> 4 -> 3 -> 2 -> 5 -> None

This Python program defines a singly linked list with methods for appending nodes, swapping two nodes, and traversing the list. The swap_nodes method uses pointers to find the nodes to be swapped and updates their next references to swap their positions in the list.