Swappnig Adjacent Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return the head pointer. Only pointer manipulation is allowed; nodde values must remain unchanged.

A sentinel node simplifies boundary handling. Maintain a prev pointer positioned immediately before each pair. In every iteration, identify the first node, the second node, and the node that follows the pair. Rewire the next references and advance prev by two positions.

The loop stops when fewer than two nodes remain. The condition must check prev->next before prev->next->next to avoid null dereference.

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* upcoming = second->next;
            
            prev->next = second;
            second->next = first;
            first->next = upcoming;
            
            prev = first;
        }
        
        ListNode* newHead = sentinel->next;
        delete sentinel;
        return newHead;
    }
};

Removing the Nth Node from the End

Remove the nth node from the end of the list in a single pass. The two-pointer technique creates a fixed-size sliding window. Initialize a dummy head and set two pointers, ahead and behind, to it. Advance ahead by n + 1 nodes so that behind ends up on the predecessor of the target node.

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0, head);
        ListNode* ahead = dummy;
        ListNode* behind = dummy;
        
        for (int i = 0; i <= n; ++i) {
            ahead = ahead->next;
        }
        
        while (ahead != nullptr) {
            ahead = ahead->next;
            behind = behind->next;
        }
        
        ListNode* target = behind->next;
        behind->next = behind->next->next;
        delete target;
        
        ListNode* result = dummy->next;
        delete dummy;
        return result;
    }
};

Finding the Intersection of Two Linked Lists

Return the first node where two singly linked lists intersect, judged by pointer equality rather than value. Because the shared portion must be a common suffix, align the two lists from the tail forward. Compute each length, advance the pointer of the longer list by the difference, then step both pointers to gether.

class Solution {
public:
    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
        int lenA = measure(headA);
        int lenB = measure(headB);
        ListNode* ptrA = headA;
        ListNode* ptrB = headB;
        
        if (lenB > lenA) {
            swap(lenA, lenB);
            swap(ptrA, ptrB);
        }
        
        int gap = lenA - lenB;
        while (gap--) {
            ptrA = ptrA->next;
        }
        
        while (ptrA != ptrB) {
            ptrA = ptrA->next;
            ptrB = ptrB->next;
        }
        return ptrA;
    }
    
private:
    int measure(ListNode* node) {
        int count = 0;
        while (node != nullptr) {
            node = node->next;
            ++count;
        }
        return count;
    }
};

Detecting the Entry Node of a Cycle

Given a linked list that may contain a cycle, return the node where the cycle begins, or null.

Phase 1: Detecting the cycle.
Use Floyd cycle-finding. A slow pointer (tortoise) moves one step at a time while a fast pointer (hare) moves two. If they meet, a cycle exists.

Phase 2: Locating the entry.
Let d1 be the distance from the head to the cycle entry, d2 from the entry to the meeting point, and d3 from the meeting point back to the entry. At the meeting moment:

• Tortoise distance: d1 + d2
• Hare distance: d1 + d2 + k(d2 + d3) for some integer k >= 1

Because the hare is twice as fast:

2(d1 + d2) = d1 + d2 + k(d2 + d3)
d1 = (k - 1)(d2 + d3) + d3

When k = 1, this simplifies to d1 = d3. Therefore, if one pointer starts at the head and another starts at the meeting point, both moving one step at a time, they will meet at the cycle entry.

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

The tortoise can never complete a full lap before being caught because the hare enters the cycle first and closes the gap at a relative speed of one node per step.