Swap Nodes in Pairs

class Solution {
public:
    ListNode* pairSwap(ListNode* head) {
        ListNode* start = new ListNode(0);
        start->next = head;
        ListNode* current = start;
        while (head && head->next) {
            ListNode* node1 = head;
            ListNode* node2 = head->next;
            current->next = node2;
            node1->next = node2->next;
            node2->next = node1;
            current = node1;
            head = node1->next;
        }
        return start->next;
    }
};

The provided C++ code implements a solution to swap every two adjacent nodes of a linked list. Here's a breakdown of how the code operates:

• A ListNode pointer named start is initialized to point to a new dummy node. This dummy node’s next pointer is set to the head of the input list. This dummy helps in handling edge cases smoothly.

• A pointer current is used for traversal, initialized to start.

• The primary logic involves a while loop that continues to run as long as there are at least two more nodes to process (head and head->next).

• Inside the loop:

  • Two pointers, node1 and node2, are initialized to head and head->next, respectively, to represent the pair of nodes to be swapped.

  • The next pointer of current is adjusted to point to node2, effectively placing node2 before node1 in the resulting list.

  • The linkage of the original next pair is maintained by setting node1->next to the node following node2 (node2->next).

  • node2->next is then set to node1 to complete the swapping of the pair.

  • To move to the next pair, current is updated to node1 and head to node1->next.

• After the loop, start->next — which points to the new head of the modified list — is returned.

This technique ensures a time complexity of O(n) and operates in-place with O(1) space complexity, making it efficient for large lists. Each pair of nodes is swapped sequentially, and the use of a dummy node simplifies the handling of head-node swaps and edge cases, like an odd number of nodes, where the last node remains in its original position if no pair is available for it.

class Solution {
    public ListNode swapAdjacentPairs(ListNode current) {
        // Initiating a dummy node to manage the edge cases smoothly
        ListNode dummy = new ListNode(0);
        dummy.next = current;

        ListNode prior = dummy;

        while ((current != null) && (current.next != null)) {
            // Identify nodes to switch
            ListNode node1 = current;
            ListNode node2 = current.next;

            // Execute swap
            prior.next = node2;
            node1.next = node2.next;
            node2.next = node1;

            // Move pointers to next pair
            prior = node1;
            current = node1.next; // advance
        }

        // Return the modified list head
        return dummy.next;
    }
}

The provided Java solution addresses the problem of swapping adjacent nodes in pairs within a singly linked list. Follow these pointers to understand the implementation:

• A dummy node is initialized at the start of the list to simplify edge case handling. This node helps manage scenarios when the list might be empty or has an odd number of nodes.

• The function operates with a while loop that continues as long as there are at least two more nodes available in the list (checked by current and current.next).

• Inside the loop:

  • Two nodes (node1 and node2) are identified as the current node and its next, respectively. These are the nodes that will be swapped.
  • The nodes are swapped by adjusting their next pointers. The prior node (initially the dummy) helps in re-linking the swapped nodes correctly back into the main list.
  • Post-swap, pointers are updated to move to the next pair. prior moves to the position of node1 (which is now after node2 post-swap), and current jumps to the next pair to continue the swap process.

• After the loop completes all possible swaps, the function returns the new head of the list, which is dummy.next. This omits the dummy from the final returned list, therefore presenting the correctly modified list.

This solution efficiently processes nodes in pairs and performs the swaps in-place, ensuring a space complexity of O(1) and a time complexity of O(n), where n is the number of nodes in the list. This makes it an optimal solution for pair swapping in singly linked lists.

struct ListNode* reorderPairs(struct ListNode* headNode) {
    struct ListNode* tempNode = malloc(sizeof(struct ListNode));
    tempNode->val = 0;
    tempNode->next = headNode;
    struct ListNode* previousNode = tempNode;
    while (headNode != NULL && headNode->next != NULL) {
        struct ListNode* node1 = headNode;
        struct ListNode* node2 = headNode->next;
        previousNode->next = node2;
        node1->next = node2->next;
        node2->next = node1;
        previousNode = node1;
        headNode = node1->next;
    }
    return tempNode->next;
}

The provided C code function reorderPairs aims to swap adjacent nodes of a linked list in pairs. This function modifies the list in-place, ensuring that the pairwise swap of nodes does not require additional memory for the nodes themselves, but only requires updating the node pointers. Here’s how the function operates:

• Initially, a temporary node tempNode is created and points to the head of the original list. This will facilitate the re-linking of nodes and will eventually help in returning the new head of the modified list.

• A previousNode is used to connect the newly swapped pairs with the rest of the list. It initially points to the tempNode.

• The function enters a while loop which continues as long as there are at least two more nodes to process. During each iteration of the while loop:

  • Two nodes node1 and node2 (where node1 is the current headNode and node2 is its next node) are identified.

  • The swap is performed by adjusting the pointers:

    • previousNode points to node2 instead of node1 to maintain the link from the previous swapped pair or the temporary starting node.
    • The next pointer of node1 is updated to point to the node following node2.
    • The next pointer of node2 is set to node1, swapping their positions.

  • previousNode is then updated to node1 to keep track of the end of the newly swapped pair.

  • The headNode is moved forward to the next node to be processed.

• After the loop, the function returns the next node of the temporary node tempNode because tempNode was only a placeholder to manage reconnections smoothly without losing the head of the list due to pair swapping.

Note, considerations for lists with an odd number of elements or lists that are empty are inherently handled by the swap logic and loop conditions. This approach ensures that the function handles all possible edge cases, such as an empty list or lists with a single node, which remain unchanged.

var swapLinkedListPairs = function(headNode) {
    let initial = new ListNode(-1);
    initial.next = headNode;
    let previous = initial;
    while (headNode !== null && headNode.next !== null) {
        let nodeOne = headNode;
        let nodeTwo = headNode.next;
        previous.next = nodeTwo;
        nodeOne.next = nodeTwo.next;
        nodeTwo.next = nodeOne;
        previous = nodeOne;
        headNode = nodeOne.next;
    }
    return initial.next;
};

The provided JavaScript function swapLinkedListPairs addresses the challenge of swapping adjacent nodes in a singly linked list. This function takes a head node of the linked list as input and returns a modified list where every two adjacent nodes are swapped. Here’s a brief explanation of how this function operates:

• An auxiliary node, initial, is created to simplify the edge cases by ensuring that the list has a dummy start node. This node points to the head of the list.
• A pointer previous is initialized to this dummy node to help in adjusting the next pointers during node swapping.
• The function enters a loop that continues until there are no two nodes left to swap (checked by headNode !== null && headNode.next !== null).
• Inside the loop:
  • Pointers nodeOne and nodeTwo are assigned to the current node and its next node respectively, which are the pair to be swapped.
  • The next pointer of previous is updated to point to nodeTwo to link the swapped nodes correctly to the part of the list already processed.
  • Adjust the next pointers of nodeOne and nodeTwo to finalize the swap.
  • Move previous and headNode pointers forward to the next pair of nodes to continue the swapping process for the remaining list.
• Once all possible swaps are done, the function returns the new head of the list from initial.next, effectively skipping over the dummy node.

This approach ensures an O(n) time complexity where n is the number of nodes in the list, and the space complexity is O(1) as it only uses a fixed amount of extra space regardless of the input size.

class Solution:
    def swapAdjacent(self, head: ListNode) -> ListNode:
        auxiliary = ListNode(0)
        auxiliary.next = head

        previous = auxiliary

        while head and head.next:
            node1 = head
            node2 = head.next

            previous.next = node2
            node1.next = node2.next
            node2.next = node1

            previous = node1
            head = node1.next

        return auxiliary.next

Swap pairs of adjacent nodes in a linked list with a given Python solution that operates in place without modifying the values within the nodes themselves.

Start by creating a dummy node, referred to as auxiliary, to simplify edge cases such as handling the head of the list. This node points initially to the head of the list.

Maintain a reference to the auxiliary node as previous. Then, proceed with a loop that traverses the nodes as long as there are at least two nodes available to swap.

Within the loop:

• Identify the current pair of nodes as 'node1' and 'node2'
• Adjust the next pointer of the previous node to point to 'node2', effectively swapping the order of 'node1' and 'node2'
• Reconfigure the next pointers of the swapped nodes to maintain the connections with other parts of the list
• Move the 'previous' position marker to the current 'node1' (originally the first of the two swapped nodes),
• Advance to the next potential pair of nodes to swap.

At the completion of the loop, the dummy node's next points to the new head of the swapped list, which is then returned as the solution.

This method ensures each pair of nodes is swapped just once, and it handles lists of different lengths (odd/even number of nodes). The space complexity remains constant, O(1), because only a few additional pointers are used.