Swap Nodes in Pairs

To swap every two adjacent nodes in a linked list without modifying the values in the list’s nodes, you can follow the following steps:

1. Create a dummy node and link it to the head of the list.
2. Use a pointer (prev) to keep track of the previous node in the swapped list.
3. Use two pointers (first and second) to refer to the two nodes that need to be swapped.
4. Adjust the links to perform the swap.
5. Update the prev pointer to the last node in the swapped pair.
6. Continue this process for every pair of nodes in the list.

Here’s the code that implements this logic:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head

        # Create a dummy node to handle the edge case when the list has only one node
        dummy = ListNode()
        dummy.next = head

        # Initialize the previous node to the dummy node
        prev = dummy

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

            # Swapping the nodes
            prev.next = second
            first.next = second.next
            second.next = first

            # Move to the next pair of nodes
            head = first.next
            prev = first

        return dummy.next

This code snippet swaps adjacent pairs in the linked list, taking care of edge cases when there are no nodes or only one node in the list. The time complexity of this solution is ( O(n) ), where ( n ) is the number of nodes in the list, and the space complexity is ( O(1) ), as we only used a constant amount of extra space.