Swap Nodes In Pairs - Leetcode Solution

The Swap Nodes in Pairs problem on Leetcode is a problem that requires swapping every two adjacent nodes in a linked list, and returning the modified list.

Here is a detailed solution to the problem:

First, we need to understand the structure of a singly linked list. A singly linked list is a sequence of nodes, with each node containing a value and a pointer to the next node in the list. The head node is the first node in the list, and the tail node is the last node in the list, with its pointer pointing to NULL.

The problem requires us to swap every two adjacent nodes in the linked list. In other words, if we have a linked list like this:

1 -> 2 -> 3 -> 4 -> 5

We need to modify it to:

2 -> 1 -> 4 -> 3 -> 5

To solve the problem, we can create a new linked list and swap every pair of adjacent nodes from the original linked list. This requires iterating over the original linked list and creating a new node for each swapped pair in the new linked list.

Here is the step-by-step algorithm to solve the problem:

1. Create a new empty linked list.

2. Initialize a pointer "prev" to NULL, which will track the last node in the new linked list.

3. Initialize a pointer "curr" to the head of the original linked list.

4. Iterate over the original linked list, swapping every pair of adjacent nodes.

5. For each pair of adjacent nodes (let's call them node1 and node2), swap them by updating their next pointers: a. Set node1's next pointer to node2's next pointer b. Set node2's next pointer to node1

6. Connect the swapped pair of nodes to the new linked list by updating the pointers of the nodes in the new linked list: a. If prev is not NULL, then set prev's next pointer to node2 (the second node of the swapped pair). b. Otherwise, set the head of the new linked list to node2 (the second node of the swapped pair).

7. Update prev to be node1 (the first node of the swapped pair).

8. Update curr to be the next node in the original linked list (which is node1's original next pointer).

9. Repeat steps 4-8 until we reach the end of the original linked list.

10. Return the head of the new linked list.

Here is the implementation of the solution in Python:

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

class Solution: def swapPairs(self, head: ListNode) -> ListNode: # Step 1: Create a new empty linked list dummy = ListNode(0) # Step 2: Initialize a pointer "prev" to NULL prev = dummy # Step 3: Initialize a pointer "curr" to the head of the original linked list curr = head

    # Step 4: Iterate over the original linked list, swapping every pair of adjacent nodes
    while curr and curr.next:
        # Step 5: Swap the pair of nodes
        node1 = curr
        node2 = curr.next
        node1.next = node2.next
        node2.next = node1
        
        # Step 6: Connect the swapped pair of nodes to the new linked list
        prev.next = node2
        
        # Step 7: Update prev to be node1
        prev = node1
        
        # Step 8: Update curr to be the next node in the original linked list
        curr = node1.next
    
    # Step 10: Return the head of the new linked list
    return dummy.next

The time complexity of the solution is O(n), where n is the number of nodes in the linked list, because we make a single pass over the original linked list. The space complexity of the solution is O(1), since we use only constant extra space.

1