Day 16 – Linked List Insertions, Reversal, Midpoint, Merge, Nth Deletion, and Addition

Insert Node at Head

Intuition: Create a new node, point it to the current head, and update the head.

Node* insertAtHead(Node* head, int val) {
    Node* newNode = new Node(val);
    newNode->next = head;
    return newNode;
}
// TC: O(1)
// SC: O(1)

---

Insert Node at End

Intuition: Traverse to the last node, attach the new node.

Node* insertAtEnd(Node* head, int val) {
    Node* newNode = new Node(val);
    if (!head) return newNode;
    Node* temp = head;
    while (temp->next) temp = temp->next;
    temp->next = newNode;
    return head;
}
// TC: O(n)
// SC: O(1)

---

Insert at K-th Position (1-based index)

Intuition: Traverse to (k-1)-th node and adjust pointers.

Node* insertAtK(Node* head, int k, int val) {
    if (k == 1) return insertAtHead(head, val);
    Node* temp = head;
    for (int i = 1; i < k - 1 && temp; i++) {
        temp = temp->next;
    }
    if (!temp) return head;
    Node* newNode = new Node(val);
    newNode->next = temp->next;
    temp->next = newNode;
    return head;
}
// TC: O(k)
// SC: O(1)

---

Insert Before Value X

Intuition: Find the node before the one containing X and insert before it.

Node* insertBeforeVal(Node* head, int val, int target) {
    if (!head) return head;
    if (head->data == target) return insertAtHead(head, val);
    Node* temp = head;
    while (temp->next && temp->next->data != target) {
        temp = temp->next;
    }
    if (!temp->next) return head;
    Node* newNode = new Node(val);
    newNode->next = temp->next;
    temp->next = newNode;
    return head;
}
// TC: O(n)
// SC: O(1)

---

Leetcode 206 – Reverse Linked List

Intuition: Change next pointers while traversing using 3 pointers (prev, curr, next).

Node* reverseList(Node* head) {
    Node* prev = NULL, *curr = head;
    while (curr) {
        Node* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}
// TC: O(n)
// SC: O(1)

---

Leetcode 876 – Middle of the Linked List

---

Method 1: Count length first

Node* middleNode(Node* head) {
    int count = 0;
    Node* temp = head;
    while (temp) count++, temp = temp->next;

    temp = head;
    for (int i = 0; i < count / 2; i++) temp = temp->next;
    return temp;
}
// TC: O(n)
// SC: O(1)

---

Method 2: Slow and Fast Pointer

Intuition: Fast moves 2x speed, so when it finishes, slow is in middle.

Node* middleNode(Node* head) {
    Node* slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}
// TC: O(n)
// SC: O(1)

---

Merge Two Sorted Linked Lists

---

Method 1: Create New List

Node* mergeTwoLists(Node* l1, Node* l2) {
    Node dummy(0);
    Node* tail = &dummy;

    while (l1 && l2) {
        if (l1->data < l2->data) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }
    tail->next = l1 ? l1 : l2;
    return dummy.next;
}
// TC: O(n + m)
// SC: O(1)

---

Method 2: In-place Recursion

Node* merge(Node* l1, Node* l2) {
    if (!l1 || !l2) return l1 ? l1 : l2;
    if (l1->data < l2->data) {
        l1->next = merge(l1->next, l2);
        return l1;
    } else {
        l2->next = merge(l1, l2->next);
        return l2;
    }
}
// TC: O(n + m)
// SC: O(n + m) recursive stack

---

Leetcode 19 – Remove N-th Node from End

---

Method 1: Count then delete

Node* removeNthFromEnd(Node* head, int n) {
    int len = 0;
    Node* temp = head;
    while (temp) len++, temp = temp->next;

    if (n == len) {
        Node* toDelete = head;
        head = head->next;
        delete toDelete;
        return head;
    }

    temp = head;
    for (int i = 1; i < len - n; i++) temp = temp->next;
    Node* toDelete = temp->next;
    temp->next = temp->next->next;
    delete toDelete;
    return head;
}
// TC: O(n)
// SC: O(1)

---

Method 2: Fast and Slow Pointers

Intuition: Move fast pointer n steps ahead, then move both until fast reaches the end.

Node* removeNthFromEnd(Node* head, int n) {
    Node* dummy = new Node(0);
    dummy->next = head;
    Node* fast = dummy, *slow = dummy;

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

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

    Node* del = slow->next;
    slow->next = slow->next->next;
    delete del;
    return dummy->next;
}
// TC: O(n)
// SC: O(1)

---

Leetcode 2 – Add Two Numbers Represented by Linked Lists

Intuition: Use carry-based addition, similar to adding two integers digit by digit.

Node* addTwoNumbers(Node* l1, Node* l2) {
    Node* dummy = new Node(0);
    Node* temp = dummy;
    int carry = 0;

    while (l1 || l2 || carry) {
        int sum = carry;
        if (l1) sum += l1->data, l1 = l1->next;
        if (l2) sum += l2->data, l2 = l2->next;
        temp->next = new Node(sum % 10);
        carry = sum / 10;
        temp = temp->next;
    }
    return dummy->next;
}
// TC: O(max(n, m))
// SC: O(max(n, m))