Swapping Adjacent Nodes in a Linked List

Swapping nodes in pairs requires careful pointer manipulation to maintain the integrity of the list structure. The core idea involves processing two nodes at a time, reversing their connection order while preserving links to neighboring nodes.

A dummy header node simplifies edge cases by providing a consistent entry point. The algorithm iterates through the list, swapping pairs until fewer than two nodes remain.

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* virtualHead = new ListNode(0);
        virtualHead->next = head;
        ListNode* current = virtualHead;
        
        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 virtualHead->next;
    }
};

Removing the Nth Node from the End

The two-pointer technique efficiently solves this problem by establishing a fixed gap between pointers. By advancing a lead pointer N steps first, then moving both pointers until the lead reaches the end, the trailing pointer lands precisely at the target node's predecessor.

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* virtualHead = new ListNode(0);
        virtualHead->next = head;
        ListNode* lead = virtualHead;
        ListNode* trail = virtualHead;
        
        for (int step = 0; step <= n; ++step) {
            lead = lead->next;
        }
        
        while (lead != nullptr) {
            lead = lead->next;
            trail = trail->next;
        }
        
        ListNode* toDelete = trail->next;
        trail->next = trail->next->next;
        delete toDelete;
        
        return virtualHead->next;
    }
};

Finding the Intersection of Two Linked Lists

Two primary approaches exist for locating where two singly linked lists converge. The first uses a hash set to record all visited nodes from one list, then checks the second list for duplicates.

class Solution {
public:
    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
        unordered_set visited;
        
        ListNode* ptr = headA;
        while (ptr != nullptr) {
            visited.insert(ptr);
            ptr = ptr->next;
        }
        
        ptr = headB;
        while (ptr != nullptr) {
            if (visited.find(ptr) != visited.end()) {
                return ptr;
            }
            ptr = ptr->next;
        }
        
        return nullptr;
    }
};

The second approach achieves O(1) space complexity by aligning the starting positions. First, calculate the length of both lists. Move the pointer of the longer list forward by the difference in lengths, ensuring both pointers are equidistant from the end. Then traverse both lists simultaneously until the intersection point is found.

class Solution {
public:
    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
        int lengthA = getListLength(headA);
        int lengthB = getListLength(headB);
        
        ListNode* ptrA = headA;
        ListNode* ptrB = headB;
        
        if (lengthA > lengthB) {
            int diff = lengthA - lengthB;
            for (int i = 0; i < diff; ++i) {
                ptrA = ptrA->next;
            }
        } else {
            int diff = lengthB - lengthA;
            for (int i = 0; i < diff; ++i) {
                ptrB = ptrB->next;
            }
        }
        
        while (ptrA != nullptr && ptrB != nullptr) {
            if (ptrA == ptrB) {
                return ptrA;
            }
            ptrA = ptrA->next;
            ptrB = ptrB->next;
        }
        
        return nullptr;
    }
    
private:
    int getListLength(ListNode* node) {
        int count = 0;
        while (node != nullptr) {
            ++count;
            node = node->next;
        }
        return count;
    }
};

Detecting the Starting Point of a Cycle

Floyd's Tortoise and Hare algorithm provides an elegant O(1) space solution. A slow pointer advances one node per iteration while a fast pointer advances two. If a cycle exists, the fast pointer will eventually meet the slow pointer inside the cycle.

Once a meeting point is confirmed, reset one pointer to the head and move both pointers one step at a time. The node where they meet again is the cycle's entry point.

class Solution {
public:
    ListNode* detectCycle(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
            
            if (slow == fast) {
                ListNode* entry = head;
                while (entry != slow) {
                    entry = entry->next;
                    slow = slow->next;
                }
                return entry;
            }
        }
        
        return nullptr;
    }
};

The mathematical reasoning behind this method relies on the relationship between distances. If the cycle starts after 'a' nodes from the head, and the meeting point is 'b' nodes into the cycle, then the distance traveled by the slow pointer equals a + b. The fast pointer travels 2(a + b). The difference, a + b, must be a multiple of the cycle length. This ensures that starting one pointer from the head and another from the meeting point will converge at the cycle's origin.