algoadvance

Leetcode 24. Swap Nodes in Pairs

Problem Statement

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list’s nodes (i.e., only nodes themselves may be changed).

Example:

Clarifying Questions

  1. What should be returned if the list is empty?
    • Return nullptr if the head of the list is nullptr.
  2. What if the list has only one node?
    • In this case, return the head as-is, since there is no pair to swap.
  3. Is the input guaranteed to be a proper singly linked list?
    • Yes, assume the input is a valid linked list.
  4. Should we handle very large linked lists?
    • Yes, the solution should be efficient and handle lists as large as can be reasonably expected for a linked list.

Strategy

To solve this problem, we will:

  1. Use a dummy node to simplify the edge cases (like the list having fewer than 2 nodes).
  2. Iterate through the list swapping nodes in pairs:
    • Identify the two nodes to swap.
    • Swap them by adjusting pointers.
    • Move to the next pair.

Code

#include <iostream>

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode dummy(0);
        dummy.next = head;
        ListNode* current = &dummy;
        
        while (current->next != nullptr && current->next->next != nullptr) {
            ListNode* first = current->next;
            ListNode* second = current->next->next;
            
            // Swapping the nodes
            first->next = second->next;
            second->next = first;
            current->next = second;
            
            // Move to the next pair
            current = first;
        }
        return dummy.next;
    }
};

// Helper function to print the linked list
void printList(ListNode* node) {
    while (node != nullptr) {
        std::cout << node->val << " -> ";
        node = node->next;
    }
    std::cout << "nullptr" << std::endl;
}

// Main function for testing purposes
int main() {
    Solution solution;

    // Creating a sample linked list 1 -> 2 -> 3 -> 4
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);

    // Print the original list
    std::cout << "Original list: ";
    printList(head);
    
    // Swapping nodes in pairs
    ListNode* newHead = solution.swapPairs(head);

    // Print the modified list
    std::cout << "Swapped list: ";
    printList(newHead);

    return 0;
}

Time Complexity

The time complexity of this algorithm is (O(n)), where (n) is the number of nodes in the linked list. This is because we traverse the list in a single pass, swapping pairs of nodes as we go.

Space Complexity

The space complexity is (O(1)) because we only use a few additional pointers, and we are not using any additional data structures that grow with the input size.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI