Linked lists are fundamental data structures that require careful pointer management. This article explores several advanced operations, including node swapping, element removal based on relative positioning, and detecting structural properties like intersections and cycles.

Swapping Nodes in Pairs

To swap adjacent nodes in a linked list, we use a sentinel (dummy) node to simplify edge cases, such as swappign the head node. The core logic involves maintaining a pointer to the node immediately preceding the pair being swapped.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* sentinel = new ListNode(0);
        sentinel->next = head;
        ListNode* prev = sentinel;

        while (prev->next != nullptr && prev->next->next != nullptr) {
            ListNode* first = prev->next;
            ListNode* second = prev->next->next;

            // Execute the swap
            first->next = second->next;
            second->next = first;
            prev->next = second;

            // Advance the pointer two steps
            prev = first;
        }
        
        ListNode* newHead = sentinel->next;
        delete sentinel;
        return newHead;
    }
};

When implemanting the loop condition, the order of prev->next and prev->next->next checks is critical to avoid null pointer dereferencing.

Removing the N-th Node From the End

A common strategy for locating a node relative to the end of a list is the "Two-Pointer" or "Fast-Slow Pointer" technique. By creating a specific gap between two pointers, we can identify the target node in a single pass.

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0, head);
        ListNode* fast = dummy;
        ListNode* slow = dummy;

        // Move fast pointer so there is a gap of n nodes between fast and slow
        for (int i = 0; i <= n; i++) {
            fast = fast->next;
        }

        // Move both until fast reaches the end
        while (fast != nullptr) {
            fast = fast->next;
            slow = slow->next;
        }

        // slow is now pointing to the node before the target
        ListNode* target = slow->next;
        slow->next = slow->next->next;
        delete target;

        ListNode* result = dummy->next;
        delete dummy;
        return result;
    }
};

Finding the Intersection of Two Linked Lists

If two linked lists intersect, they must share the same tail. By calculating the lengths of both lists, we can align their starting positions and traverse them simultaneously to find the first common node.

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int lenA = 0, lenB = 0;
        ListNode *ptrA = headA, *ptrB = headB;

        while (ptrA) { lenA++; ptrA = ptrA->next; }
        while (ptrB) { lenB++; ptrB = ptrB->next; }

        ptrA = headA;
        ptrB = headB;

        // Ensure ptrA points to the longer list
        if (lenB > lenA) {
            std::swap(lenA, lenB);
            std::swap(ptrA, ptrB);
        }

        // Align the starting positions
        int diff = lenA - lenB;
        while (diff--) {
            ptrA = ptrA->next;
        }

        // Traverse together until an intersection is found
        while (ptrA != nullptr) {
            if (ptrA == ptrB) return ptrA;
            ptrA = ptrA->next;
            ptrB = ptrB->next;
        }

        return nullptr;
    }
};

Detecting the Entrance of a Cycle

Detecting a cycle is often done using Floyd's Cycle-Finding Algorithm. Once a cycle is confirmed, a mathematical relationship allows us to find the entry point: the distance from the head to the entrance is equal to the distance from the meeting point to the entrance.

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;

            // Cycle detected
            if (slow == fast) {
                ListNode* index1 = head;
                ListNode* index2 = fast;
                
                // Find the entry point
                while (index1 != index2) {
                    index1 = index1->next;
                    index2 = index2->next;
                }
                return index1;
            }
        }
        return nullptr;
    }
};