Pairwise Swapping of Adjacetn Nodes in a Linked List

Given a linked list, swap every two adjacent nodes and return the head of the modified list. The operation must be performed by exchanging nodes, not by altering their internal values.

Implementation approach: Use a dummy head node to simplify edge cases. Iterate through the list, adjusting pointers to swap pairs.

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* current = dummy;
        while (current->next && current->next->next) {
            ListNode* first = current->next;
            ListNode* second = first->next;
            ListNode* third = second->next;
            
            current->next = second;
            second->next = first;
            first->next = third;
            
            current = first;
        }
        ListNode* result = dummy->next;
        delete dummy;
        return result;
    }
};

When creating a dummy node, allocate memory on the heap using new. Ensure to deallocate it after use to prevent memory leaks.

Removing the Nth Node from the End Using Two Pointers

Delete the node that is the nth from the end of a linked list and return the head.

Utilize a two-pointer technique: advance a fast pointer n+1 steps ahead, then move both pointers simultaneously untill the fast pointer reaches the end. The slow pointer will then be positioned just before the target node.

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* sentinel = new ListNode(0);
        sentinel->next = head;
        ListNode* lead = sentinel;
        ListNode* trail = sentinel;
        
        for (int i = 0; i <= n; ++i) {
            lead = lead->next;
        }
        
        while (lead) {
            lead = lead->next;
            trail = trail->next;
        }
        
        ListNode* toDelete = trail->next;
        trail->next = toDelete->next;
        delete toDelete;
        
        ListNode* newHead = sentinel->next;
        delete sentinel;
        return newHead;
    }
};

Deallocate the removed node to avoid memory leaks.

Finding the Intersection Node of Two Linked Lists

Given two singly linked lists, return the node where they intersect. If no intersection exists, return null. The original structure of both lists must remain unchanged.

Strategy: Calculate the lengths of both lists. Align the starting points by advancing the pointer of the longer list by the difference in lengths. Then traverse both lists together until a common node is found.

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int lenA = 0, lenB = 0;
        ListNode* ptrA = headA;
        ListNode* ptrB = headB;
        
        while (ptrA) {
            lenA++;
            ptrA = ptrA->next;
        }
        while (ptrB) {
            lenB++;
            ptrB = ptrB->next;
        }
        
        ptrA = headA;
        ptrB = headB;
        
        if (lenA > lenB) {
            for (int i = 0; i < lenA - lenB; ++i) {
                ptrA = ptrA->next;
            }
        } else {
            for (int i = 0; i < lenB - lenA; ++i) {
                ptrB = ptrB->next;
            }
        }
        
        while (ptrA && ptrB) {
            if (ptrA == ptrB) {
                return ptrA;
            }
            ptrA = ptrA->next;
            ptrB = ptrB->next;
        }
        return nullptr;
    }
};

Detecting the Start of a Cycle in a Linked List

Return the node where a cycle begins in a linked list. If no cycle exists, return null.

Approach: Use two pointers, one moving twice as fast as the other. Upon detecting a meeting point, reset one pointer to the head and move both at the same pace until they meet again at the cycle's entry point.

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

In the loop condition fast && fast->next, the logical AND operator evaluates left to right, ensuring fast->next is only accessed when fast is non-null.