Linked List Problems

Replace Linked List on Index

a0 -> a1(beforeLo) -> a2(lo) -> a3 (hi)-> a4(afterHi)….an

b0 -> b1 -> b2 … bn

after the operation, we will have

a0 -> a1(beforeLo) ->[b0…bn]-> a4(afterHi)….an

The critical part is find the beforeLo and afterHi nodes. Meanwhile, in order to address the edge case of lo = 0, we add dummy value at the beginning.

/**
 * class LLNode {
 *     public:
 *         int val;
 *         LLNode *next;
 * };
 */
LLNode* solve(LLNode* a, LLNode* b, int lo, int hi) {
    auto dummy = new LLNode();
    dummy -> next = a;
    auto dummy1 = dummy;
    auto curr = dummy;
    int idx =0;
    auto beforeLo = a, afterHi = a;
    // find beforeLo and afterHi
    while (curr->next){
        if (idx == lo){
             beforeLo = curr;
        }
        if (idx == hi){
             afterHi = curr -> next -> next;
        }
        curr = curr->next;
        idx++;
    }
    // put b between beforeLo and afterHi
    if (b == nullptr){
        beforeLo -> next = afterHi;
    } else {
        beforeLo -> next = b;
        while (b -> next){
            b = b->next;
        }
        b -> next = afterHi;
    }
    return dummy1 -> next;
    
}