inserting a node before another node with the same value in java

Question

I am trying to insert a node before a given value in a linked list, recursively. I can add the value anywhere in the middle of the list, but I am struggling to add a node to the start of the list. Here is my code so far:

/** insertValueBeforeEveryX
 * 
 *  Preconditions:  list may be empty,   X and Value are not equal
 *  
 *  insert a new node containing  Value  before every node containing X
 *  
 *  you can write this iteratively or recursively,  but you should only have one loop or recursive helper
 *  you may not call any other method (e.g.  size  )

 *  
 *   { }.insertValueBeforeEveryX(9,2)           -->  { }                // initial list was empty
 *   { 1 1 1 1 }.insertValueBeforeEveryX(9,2)   -->  { 1 1 1 1  }       // 0 occurrences of '2'
 *   { 2 }.insertValueBeforeEveryX(9,2)         -->  { 9 2}             // 1 occurrence of '2'
 *   { 1 2 3 2 }.insertValueBeforeEveryX(9,2)   -->  { 1 9 2 3 9 2}     // 2 occurrences of '2'
 *   
 */
public void insertValueBeforeEveryX (int value, int X ) {
    insertValueBeforeEveryXHelper(first, value, X, null);
}

private void insertValueBeforeEveryXHelper(Node x, int val, int check, Node prev)  {
    if(x == null) return;

    if(x.item == check && prev == null) {
        prev = new Node(val, x);
    } else {
        if(x.item == check && prev != null) {
            prev.next = new Node(val, x);
        }
    }
    insertValueBeforeEveryXHelper(x.next, val, check, x);
}

Output: Success { }.insertValueBeforeEveryX(1,99): Result: { }
Failed { 99 }.insertValueBeforeEveryX(1,99): Expecting { 1 99 } Actual { 99 } Success { 88 }.insertValueBeforeEveryX(1,99): Result: { 88 }
Failed { 99 10 }.insertValueBeforeEveryX(1,99): Expecting { 1 99 10 } Actual { 99 10 } Success { 10 99 }.insertValueBeforeEveryX(1,99): Result: { 10 1 99 }
Failed { 99 10 99 }.insertValueBeforeEveryX(1,99): Expecting { 1 99 10 1 99 } Actual { 99 10 1 99 } Success { 5 99 6 99 99 7 }.insertValueBeforeEveryX(1,99): Result: { 5 1 99 6 1 99 1 99 7 }

Any help to explain what I am doing wrong would be greatly appreciated.

Answer 1

You forgot to update the reference to the first element of the linked list.

See first = prev; below

   // [...]

private void insertValueBeforeEveryXHelper(Node x, int val, int check, Node prev)  {
    if(x == null) return;

    if(x.item == check && prev == null) {
        prev = new Node(val, x);
        first = prev;
    } else {
        // [...]
    }       
}