Day 17 – Advanced Linked Lists + Trapping Rainwater

Leetcode 237. Delete Node in a Linked List

Intuition: You’re given access to the node itself, not the head. Copy data from next node, then delete the next node.

void deleteNode(ListNode* node) {
    node->val = node->next->val;
    node->next = node->next->next;
}
// TC: O(1)
// SC: O(1)

---

Leetcode 160. Intersection of Two Linked Lists

---

1. Brute Force

Check each node of list A against all nodes of B.

• TC: O(m * n)

• SC: O(1)

---

2. Hashing

Store nodes of A in a set, then check B.

ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
    unordered_set<ListNode*> st;
    while (headA) st.insert(headA), headA = headA->next;
    while (headB) {
        if (st.count(headB)) return headB;
        headB = headB->next;
    }
    return NULL;
}
// TC: O(m + n)
// SC: O(m)

---

3. Two Pointers (Optimal)

Intuition: Equalize path length by switching heads after reaching null.

ListNode* getIntersectionNode(ListNode* a, ListNode* b) {
    ListNode* t1 = a, *t2 = b;
    while (t1 != t2) {
        t1 = t1 ? t1->next : b;
        t2 = t2 ? t2->next : a;
    }
    return t1;
}
// TC: O(m + n)
// SC: O(1)

---

Leetcode 141. Linked List Cycle

---

1. Hashing

bool hasCycle(ListNode* head) {
    unordered_set<ListNode*> seen;
    while (head) {
        if (seen.count(head)) return true;
        seen.insert(head);
        head = head->next;
    }
    return false;
}
// TC: O(n)
// SC: O(n)

---

2. Tortoise-Hare

bool hasCycle(ListNode *head) {
    if (!head || !head->next) return false;
    ListNode* slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}
// TC: O(n)
// SC: O(1)

---

Leetcode 25. Reverse Nodes in K Group

---

1. Iterative

ListNode* reverseKGroup(ListNode* head, int k) {
    ListNode* curr = head;
    int count = 0;
    while (curr && count < k) {
        curr = curr->next;
        count++;
    }
    if (count < k) return head;

    curr = reverseKGroup(curr, k);
    while (count--) {
        ListNode* temp = head->next;
        head->next = curr;
        curr = head;
        head = temp;
    }
    return curr;
}
// TC: O(n)
// SC: O(n/k) -> recursion stack

---

Leetcode 234. Palindrome Linked List

Intuition: Use slow/fast pointer to find mid, reverse second half and compare.

bool isPalindrome(ListNode* head) {
    if (!head || !head->next) return true;
    ListNode* slow = head, *fast = head;
    while (fast->next && fast->next->next)
        slow = slow->next, fast = fast->next->next;

    ListNode* prev = NULL, *curr = slow->next;
    while (curr) {
        ListNode* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }

    ListNode* first = head, *second = prev;
    while (second) {
        if (first->val != second->val) return false;
        first = first->next, second = second->next;
    }
    return true;
}
// TC: O(n)
// SC: O(1)

---

Leetcode 142. Linked List Cycle II

Intuition: Floyd's algo detects the cycle. Reset one pointer and move both at same speed.

ListNode *detectCycle(ListNode *head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            while (head != slow) {
                head = head->next;
                slow = slow->next;
            }
            return head;
        }
    }
    return NULL;
}
// TC: O(n)
// SC: O(1)

---

Flattening a Multilevel Linked List

---

Brute Force

Use array to store all values and recreate list.

• TC: O(n)

• SC: O(n)

---

Recursive Approach

Intuition: Merge next list into current level’s child list recursively.

Node* merge(Node* a, Node* b) {
    if (!a) return b;
    if (!b) return a;
    if (a->data < b->data) {
        a->bottom = merge(a->bottom, b);
        return a;
    } else {
        b->bottom = merge(a, b->bottom);
        return b;
    }
}

Node* flatten(Node* root) {
    if (!root || !root->next) return root;
    root->next = flatten(root->next);
    return merge(root, root->next);
}
// TC: O(N*M) (N: vertical lists, M: nodes in each)
// SC: O(1) (no extra list created)

---

Leetcode 61. Rotate Linked List

---

1. Brute Force

Rotate 1 step k times.

• TC: O(k * n)

• SC: O(1)

---

2. Optimal

Intuition: Connect last node to head to form a loop. Break it at the right point.

ListNode* rotateRight(ListNode* head, int k) {
    if (!head || !head->next || k == 0) return head;

    int len = 1;
    ListNode* tail = head;
    while (tail->next) {
        len++;
        tail = tail->next;
    }

    tail->next = head; // circular
    k = k % len;
    int steps = len - k;
    while (steps--) tail = tail->next;

    head = tail->next;
    tail->next = NULL;
    return head;
}
// TC: O(n)
// SC: O(1)

---

Leetcode 138. Copy List with Random Pointer

---

1. Using Map

Node* copyRandomList(Node* head) {
    unordered_map<Node*, Node*> mp;
    Node* temp = head;
    while (temp) {
        mp[temp] = new Node(temp->val);
        temp = temp->next;
    }
    temp = head;
    while (temp) {
        mp[temp]->next = mp[temp->next];
        mp[temp]->random = mp[temp->random];
        temp = temp->next;
    }
    return mp[head];
}
// TC: O(n)
// SC: O(n)

---

2. Optimal (No extra space)

Intuition: Clone nodes in between original ones, then fix randoms, then split.

Node* copyRandomList(Node* head) {
    if (!head) return NULL;

    Node* temp = head;
    while (temp) {
        Node* clone = new Node(temp->val);
        clone->next = temp->next;
        temp->next = clone;
        temp = clone->next;
    }

    temp = head;
    while (temp) {
        if (temp->random) temp->next->random = temp->random->next;
        temp = temp->next->next;
    }

    Node* dummy = new Node(0);
    Node* copy = dummy;
    temp = head;
    while (temp) {
        copy->next = temp->next;
        temp->next = temp->next->next;
        temp = temp->next;
        copy = copy->next;
    }
    return dummy->next;
}
// TC: O(n)
// SC: O(1)

---

Leetcode 42. Trapping Rainwater

---

1. Brute Force

For each index, calculate max on left and right.

• TC: O(n²)

• SC: O(1)

---

2. Prefix & Suffix Arrays

int trap(vector<int>& height) {
    int n = height.size();
    vector<int> left(n), right(n);
    left[0] = height[0];
    for (int i = 1; i < n; i++) left[i] = max(left[i - 1], height[i]);
    right[n - 1] = height[n - 1];
    for (int i = n - 2; i >= 0; i--) right[i] = max(right[i + 1], height[i]);

    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans += min(left[i], right[i]) - height[i];
    }
    return ans;
}
// TC: O(n)
// SC: O(n)

---

3. Two Pointers

Intuition: Track leftMax and rightMax while iterating from both sides.

int trap(vector<int>& height) {
    int l = 0, r = height.size() - 1, leftMax = 0, rightMax = 0, ans = 0;
    while (l <= r) {
        if (height[l] <= height[r]) {
            leftMax = max(leftMax, height[l]);
            ans += leftMax - height[l++];
        } else {
            rightMax = max(rightMax, height[r]);
            ans += rightMax - height[r--];
        }
    }
    return ans;
}
// TC: O(n)
// SC: O(1)