Swapping Nodes in Pairs

Approach: Using a dummy head node

Logic: Create a dummy head node to simplify the swapping process. Use a current pointer that moves forward two steps at a time. The loop continues as long as there are at least two more nodes to swap.

Implementation:

/**
 * 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* dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode* current = dummyHead;
        
        while (current != nullptr && current->next != nullptr && current->next->next != nullptr) {
            ListNode* first = current->next;
            ListNode* second = current->next->next;
            ListNode* third = second->next;
            
            current->next = second;
            second->next = first;
            first->next = third;
            
            current = current->next->next;
        }
        return dummyHead->next;
    }
};

Removing the Nth Node from End

Approach 1: Calculate length and position

Logic: First, determine the length of the linked list. Then, find the node at position (length - n) and skip the next node to remove the nth node from the end.

Implementation:

/**
 * 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) {
        int length = 0;
        ListNode* temp = head;
        while (temp != nullptr) {
            temp = temp->next;
            length++;
        }
        
        ListNode* dummyHead = new ListNode(0, head);
        ListNode* current = dummyHead;
        for (int i = 0; i < length - n; i++) {
            current = current->next;
        }
        current->next = current->next->next;
        return dummyHead->next;
    }
};

Approach 2: Two pointers technique

Logic: Use two pointers with a gap of n nodes between them. When the fast pointer reaches the end, the slow pointer will be at the node before the one to be removed.

Implementation:

/**
 * 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* dummyHead = new ListNode(0, head);
        ListNode* fast = dummyHead;
        ListNode* slow = dummyHead;
        
        // Move fast n+1 steps ahead
        for (int i = 0; i < n + 1; i++) {
            fast = fast->next;
        }
        
        // Move both pointers until fast reaches the end
        while (fast != nullptr) {
            fast = fast->next;
            slow = slow->next;
        }
        
        // Remove the nth node from the end
        slow->next = slow->next->next;
        return dummyHead->next;
    }
};

Intersection of Two Linked Lists

Approach: Two pointers with length adjustment

Logic: Calculate the lengths of both lists. Move the pointer of the longer list ahead by the difference in lengths. Then move both pointers until they meet at the intersection point.

Implementation:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    int getListLength(ListNode* node) {
        int length = 0;
        while (node != NULL) {
            node = node->next;
            length++;
        }
        return length;
    }
    
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int lenA = getListLength(headA);
        int lenB = getListLength(headB);
        
        ListNode* ptrA = headA;
        ListNode* ptrB = headB;
        
        // Move the pointer of the longer list ahead
        if (lenA > lenB) {
            int diff = lenA - lenB;
            while (diff--) {
                ptrA = ptrA->next;
            }
        } else {
            int diff = lenB - lenA;
            while (diff--) {
                ptrB = ptrB->next;
            }
        }
        
        // Find the intersection point
        while (ptrA != NULL) {
            if (ptrA == ptrB) {
                return ptrA;
            }
            ptrA = ptrA->next;
            ptrB = ptrB->next;
        }
        
        return NULL;
    }
};

Detecting Cycle in Linked List

Approach: Floyd's Cycle Detection Algorithm

Logic: Use two pointers moving at different speeds. If there's a cycle, they will eventually meet. Then, to find the cycle's entry point, reset one pointer to the head and move both at the same speed until they meet again.

Implementation:

/**
 * 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) {
        // Find the meeting point
        ListNode *fast = head;
        ListNode *slow = head;
        
        while (fast != NULL && fast->next != NULL && fast->next->next != NULL) {
            fast = fast->next->next;
            slow = slow->next;
            
            if (fast == slow) {
                // Find the cycle entrance
                ListNode *ptr1 = head;
                ListNode *ptr2 = fast;
                
                while (ptr1 != ptr2) {
                    ptr1 = ptr1->next;
                    ptr2 = ptr2->next;
                }
                return ptr1;
            }
        }
        
        return NULL;
    }
};