Pairwise Node Swapping

To swap adjacent nodes in pairs, we utilize a dummy node to simplify edge cases. The core idea involves manipulating pointers to reverse each pair while maintaining proper linkage with the rest of the list. A cursor pointer tracks the predecessor of each pair being processed.

The termination condition varies based on whether the total number of nodes is odd or even. For odd counts, processing stops when only one node remains unpaired (cur->next->next becomes null). For even counts, the loop ends when cur->next reaches null.

typedef ListNode node;
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (!head || !head->next) return head;
        
        node* sentinel = new ListNode();
        sentinel->next = head;
        node* tracker = sentinel;
        
        while (tracker && tracker->next && tracker->next->next) {
            node* first = tracker->next;
            node* second = first->next;
            
            tracker->next = second;
            first->next = second->next;
            second->next = first;
            tracker = first;
        }
        
        return sentinel->next;
    }
};

Removing Nth Node from End

Using two pointers with a fixed distance enables single-pass removal. Initially, advance the leading pointer n steps ahead of the trailing pointer. When the leader reaches the end, the follower points to the target node for deletion.

An optimized version advances the leader n+1 steps, positioning the follower at the predecessor of the target node for direct removal.

typedef ListNode node;
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if (!head) return head;
        
        node* guard = new ListNode();
        guard->next = head;
        node* leader = guard;
        node* follower = guard;
        
        for (int i = 0; i <= n; ++i) {
            if (!leader) return guard->next;
            leader = leader->next;
        }
        
        while (leader) {
            leader = leader->next;
            follower = follower->next;
        }
        
        node* target = follower->next;
        follower->next = target->next;
        delete target;
        
        return guard->next;
    }
};

Intersection Point Detection

To locate where two linked lists intersect, calculate their lengths and align the starting positions accordingly. The longer list's pointer advances by the length difference before both pointers move simultaneously. If they meet before reaching null, that meeting point is the intersection.

typedef ListNode* node;
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *firstHead, ListNode *secondHead) {
        if (!firstHead || !secondHead) return nullptr;
        
        node ptr1 = firstHead;
        node ptr2 = secondHead;
        int len1 = 0, len2 = 0;
        
        while (ptr1) {
            ptr1 = ptr1->next;
            len1++;
        }
        
        while (ptr2) {
            ptr2 = ptr2->next;
            len2++;
        }
        
        ptr1 = firstHead;
        ptr2 = secondHead;
        
        if (len1 < len2) {
            std::swap(ptr1, ptr2);
            std::swap(len1, len2);
        }
        
        for (int i = 0; i < len1 - len2; ++i)
            ptr1 = ptr1->next;
        
        while (ptr1 && ptr2 && ptr1 != ptr2) {
            ptr1 = ptr1->next;
            ptr2 = ptr2->next;
        }
        
        return ptr1;
    }
};

Cycle Detection and Entry Point

Cycle detection uses Floyd's Tortoise and Hare algorithm. Two pointers move at different speeds—when they meet, a cycle exists. To find the cycle's entry point, reset one pointer to the head while keeping the other at the meeting point. Moving both at equal speed leads them to converge at the cycle entrance.

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

Middle Node Identification

Finding the middle element employs the same two-pointer technique. With one pointer moving twice as fast as the other, when the faster reaches the end, the slower sits at the midpoint. For even-length lists, an additional check ensures the latter middle node is returned.

typedef ListNode* node;
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        node anchor = new ListNode();
        anchor->next = head;
        node walker = anchor;
        node runner = anchor;
        
        while (runner && runner->next) {
            walker = walker->next;
            runner = runner->next->next;
        }
        
        if (runner && !runner->next) 
            return walker->next;
        return walker;
    }
};