24. Swap Nodes in Pairs

Problem Link: LeetCode 24

Solution:
This problem involves swapping adjacent nodes in a linked list in pairs. A dummy head node simplifies edge case handling, such as when the list has only one or two nodes.

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

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;

            first->next = second->next;
            second->next = first;
            current->next = second;

            current = current->next->next;
        }

        return dummy->next;
    }
};

19. Remove Nth Node From End of List

Problem Link: LeetCode 19

Solution:
This solution uses a two-pointer approach. The first pointer advances N steps ahead, then both move untill the first reaches the end. The second pointer will then be at the node before the one to remove.

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

        for (int i = 0; i <= n; ++i) {
            fast = fast->next;
        }

        while (fast) {
            fast = fast->next;
            slow = slow->next;
        }

        slow->next = slow->next->next;
        return dummy->next;
    }
};

Interview Qeustion 02.07. Intersection of Two Linked Lists

Problem Link: LeetCode 02.07

Solution:
This solution compares two linked lists to find their intersection node. It first caluclates the lengths of both lists, then aligns the starting points by advancing the longer list's pointer by the difference in lengths.

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

        while (a) {
            lenA++;
            a = a->next;
        }

        while (b) {
            lenB++;
            b = b->next;
        }

        a = headA;
        b = headB;

        if (lenA < lenB) {
            swap(lenA, lenB);
            swap(a, b);
        }

        int diff = lenA - lenB;
        while (diff--) {
            a = a->next;
        }

        while (a && b) {
            if (a == b) return a;
            a = a->next;
            b = b->next;
        }

        return nullptr;
    }
};

142. Linked List Cycle II

Problem Link: LeetCode 142

Solution:
This solution detects the start of a cycle in a linked list using Floyd’s Cycle Detection Algorithm. It uses two pointers: one fast and one slow. Once a cycle is detected, a second traversal identifies the cycle's entry point.

class Solution {
public:
    ListNode* detectCycle(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;

        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;

            if (slow == fast) {
                ListNode* entry = head;
                while (entry != slow) {
                    entry = entry->next;
                    slow = slow->next;
                }
                return entry;
            }
        }

        return nullptr;
    }
};