Sentinel Node Strategy

A dummy or sentinel node simplifies edge cases where the head pointer might change. By initializing a new node that points to the original head, operations such as deletion or swapping can be treated uniformly with out special casing the start of the list.

auto* sentry = new ListNode(0);
sentry->next = head;

24. Swap Nodes in Pairs

To swap adjacent nodes efficiently, track three pointers: the predecessor (sentry), the first node of the pair, and the second node. A temporary buffer is required to preserve the link to the subsequent segment before breaking the current connections.

Algorithm Steps:

1. Point the predecessor to the second node of the pair.
2. Link the first node to the successor of the second node.
3. Link the second node back to the first node.
4. Advance the predecessor two steps for the next iteration.

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        auto* sentry = new ListNode(0);
        sentry->next = head;
        auto* currentPtr = sentry;

        while (currentPtr->next != nullptr && currentPtr->next->next != nullptr) {
            auto* firstNode = currentPtr->next;
            auto* secondNode = currentPtr->next->next;
            auto* afterPair = secondNode->next;

            // Perform the re-arrangement
            currentPtr->next = secondNode;
            secondNode->next = firstNode;
            firstNode->next = afterPair;

            // Move cursor forward by two positions
            currentPtr = firstNode;
        }

        auto* resultHead = sentry->next;
        delete sentry; // Clean up allocated memory
        return resultHead;
    }
};

19. Remove Nth Node From End

To remove a node from the end without counting total length twice, maintain a gap between a fast pointer and a slow pointer. The distance is set to n + 1 when both start at the sentinel. Once fast reaches the end, slow will be positioned exactly before the target node.

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        auto* sentry = new ListNode(0);
        sentry->next = head;
        
        auto* fastPtr = sentry;
        auto* slowPtr = sentry;

        // Move fast pointer ahead by n steps
        for (int i = 0; i < n; ++i) {
            if (fastPtr) fastPtr = fastPtr->next;
        }
        // Move one extra step to ensure slowPtr lands on the predecessor
        if (fastPtr) fastPtr = fastPtr->next;

        // Advance both until fast reaches tail
        while (fastPtr != nullptr) {
            fastPtr = fastPtr->next;
            slowPtr = slowPtr->next;
        }

        // Bypass the target node
        auto* targetToDelete = slowPtr->next;
        slowPtr->next = slowPtr->next->next;
        delete targetToDelete; // Manual memory management
        
        auto* newHead = sentry->next;
        delete sentry;
        return newHead;
    }
};

Intersection of Two Linked Lists

Intersection implies sharing the same memory address from a specific node onward. To locate this point, calculate the length of both lists. Align the starting position of the longer list with the shorter list's end, then iterate both simultaneously until they meet.

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (!headA || !headB) return nullptr;

        auto* currA = headA;
        auto* currB = headB;
        size_t lenA = 0;
        size_t lenB = 0;

        while (currA) { lenA++; currA = currA->next; }
        while (currB) { lenB++; currB = currB->next; }

        currA = headA;
        currB = headB;

        // Ensure A is the longer list
        if (lenB > lenA) {
            std::swap(currA, currB);
            std::swap(lenA, lenB);
        }

        // Advance the longer list by the difference
        int diff = static_cast<int>(lenA - lenB);
        while (diff--) {
            currA = currA->next;
        }

        // Traverse together to find intersection
        while (currA && currB) {
            if (currA == currB) return currA;
            currA = currA->next;
            currB = currB->next;
        }

        return nullptr;
    }
};

Linked List Cycle II

Detecting the cycle entry relies on the mathematical relationship derived from Floyd’s Tortoise and Hare algorithm. If a cycle exists, resetting one pointer to the head and moving both one step at a time will cause them to meet exactly at the cycle entrance.

class Solution {
public:
    ListNode *detectCycle(ListNode* head) {
        auto* slowPtr = head;
        auto* fastPtr = head;

        // Phase 1: Detect loop
        while (fastPtr && fastPtr->next) {
            slowPtr = slowPtr->next;
            fastPtr = fastPtr->next->next;

            if (slowPtr == fastPtr) {
                // Phase 2: Find entry point
                auto* entryPtr = head;
                while (entryPtr != slowPtr) {
                    entryPtr = entryPtr->next;
                    slowPtr = slowPtr->next;
                }
                return entryPtr;
            }
        }
        return nullptr;
    }
};

Engineering Considerations

When implementing linked list algorithms, several best practices reduce errors:

1. Memory Management: In environments requiring manual garbage collection (like C++), any node deleted dynamically must be tracked via delete. Allocating sentinel nodes also requires cleanup post-operation.
2. Null Pointer Safety: Always validate ptr->next before dereferencing. Check conditions like ptr && ptr->next in loops to prevent segmentation faults.
3. Pointer Arithmetic: Changing next links severs existing paths. Always store necessary future references in temporary variables before overwriting next pointers.
4. Sentinel Utility: Using a dummy head removes branching logic for empty lists or head deletions, keeping the main control flow linear.