Swapping Adjacent Nodes in Pairs

Manipulating node connections uniformly requires a sentinel (dummy) node to eliminate edge cases for the head element. To exchange adjacent pairs, position a reference pointer immediately before the pair undergoing modification.

The iterative approach tracks three critical references: the node preceding the pair, the first node of the pair, and the subsequent node following the pair. This prevents reference loss during pointer reassignment.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
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;
            ListNode* remainder = second->next;
            
            prev->next = second;
            second->next = first;
            first->next = remainder;
            
            prev = first;
        }
        
        return sentinel->next;
    }
};

Removing the Nth Node from the End

A single-pass solution employs two references maintaining a fixed distance of n+1 nodes apart. Initialize a lead pointer n+1 nodes ahead of a trail pointer. When the lead reaches the list terminus (nullptr), the trail pointer rests immediately before the target node, enabling straightforward deletion.

A guard node ensures uniform handling regardless of whether the head itself requires removal.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* guard = new ListNode(0);
        guard->next = head;
        ListNode* lead = guard;
        ListNode* trail = guard;
        
        for (int i = 0; i <= n; ++i) {
            lead = lead->next;
        }
        
        while (lead != nullptr) {
            lead = lead->next;
            trail = trail->next;
        }
        
        ListNode* target = trail->next;
        trail->next = target->next;
        delete target;
        
        return guard->next;
    }
};

Locating the Cycle Entry Point

Floyd's Cycle-Finding Algorithm identifies both the prseence and origin of a circular structure through two distinct phases.

Phase One: Inetrsection Detection Initialize two pointers, tortoise and hare, at the list origin. Advance the tortoise by one node and the hare by two nodes per iteration. If the list is linear, the hare reaches the end. If cyclic, the pointesr converge within the loop. At convergence, the tortoise has traveled $k$ nodes while the hare travels $2k$, where $k$ represents an integer multiple of the cycle length.

Phase Two: Entry Identification Upon collision, reset the hare to the list head while maintaining the tortoise position. Advance both pointers at identical speeds (one node per step). Their subsequent meeting point occurs exactly at the cycle's entry node, located $a$ nodes from the head (where $a$ denotes the non-cyclic prefix length).

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (head == nullptr || head->next == nullptr) {
            return nullptr;
        }
        
        ListNode* tortoise = head;
        ListNode* hare = head;
        
        do {
            if (hare == nullptr || hare->next == nullptr) {
                return nullptr;
            }
            tortoise = tortoise->next;
            hare = hare->next->next;
        } while (tortoise != hare);
        
        hare = head;
        while (tortoise != hare) {
            tortoise = tortoise->next;
            hare = hare->next;
        }
        
        return hare;
    }
};