Solution For Swap Nodes In Pairs

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.

Step by Step Implementation For Swap Nodes In Pairs

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        // if head is null or there is only one node in the linked list
        if(head == null || head.next == null) {
            return head;
        }
        
        // we will need to keep track of the previous node
        // so that we can connect the swapped nodes later
        ListNode prev = null;
        
        // we will also need a reference to the current head
        // so that we can return it later
        ListNode currHead = head;
        
        // we will use a while loop to iterate through the linked list
        while(head != null && head.next != null) {
            // we will need to keep track of the next node
            // so that we do not lose track of any nodes
            ListNode next = head.next.next;
            
            // now we can swap the nodes
            head.next.next = head;
            head.next = next;
            
            // if this is the first swap, we need to update the currHead
            if(prev == null) {
                currHead = head.next;
            }
            // otherwise, we need to connect the previous node to the swapped nodes
            else {
                prev.next = head.next;
            }
            
            // finally, we need to update prev and head
            prev = head;
            head = next;
        }
        
        // we will return the currHead which should now be pointing to the first swapped node
        return currHead;
    }
}

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        # if there are no nodes or only one node, return head
        if not head or not head.next:
            return head
        # create a new head for the list
        new_head = head.next
        # set the first node's next to the third node
        head.next = head.next.next
        # set the second node's next to the first node
        new_head.next = head
        # recursively call the function on the remaining nodes
        new_head.next.next = self.swapPairs(new_head.next.next)
        # return the new head of the list
        return new_head

var swapPairs = function(head) {
    // if the list has no nodes or only one node, return the list as is
    if (!head || !head.next) {
        return head;
    }
    
    // initialize pointers for current node, next node, and previous node
    let curr = head;
    let next = head.next;
    let prev = null;
    
    // loop through the list, swapping nodes in pairs
    while (curr && next) {
        // if this is the first node in the list, update head to point to the next node
        if (!prev) {
            head = next;
        } else {
            // otherwise, connect the previous node to the next node
            prev.next = next;
        }
        
        // swap the next node and the current node
        curr.next = next.next;
        next.next = curr;
        
        // update previous node to be the current node
        prev = curr;
        
        // update the current node and next node to be the next nodes in the list
        curr = curr.next;
        next = curr ? curr.next : null;
    }
    
    return head;
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(head == nullptr || head->next == nullptr) {
            return head;
        }
        
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* current = dummy;
        
        while(current->next != nullptr && current->next->next != nullptr) {
            ListNode* first = current->next;
            ListNode* second = current->next->next;
            
            current->next = second;
            first->next = second->next;
            second->next = first;
            
            current = first;
        }
        
        return dummy->next;
    }
};

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode SwapPairs(ListNode head) {
        //if the list is empty or consists of only one node, return it
        if(head == null || head.next == null){
            return head;
        }
        
        //store the first node in a temporary variable
        ListNode temp = head;
        
        //store the second node in a temporary variable
        ListNode temp2 = head.next;
        
        //set the first node to point to the third node
        head = temp2.next;
        
        //set the second node to point to the first node
        temp2.next = temp;
        
        //set the first node to point to the second node
        temp.next = SwapPairs(head);
        
        //return the second node
        return temp2;
    }
}