Rewrite the insertBefore() method. Remove the existing iterative implementation of the method, and replace it with one that uses recursion instead. No loops are allowed.

/** * insertBefore - inserts the specified new character (newChar) * before the first occurrence of the specified character (afterChar) * in the linked-list string to which str refers. * If beforeChar is not in the string, the method adds the character * to the end of the string. Returns a reference to the first node * in the modified linked list, because the first node can change. */ public static StringNode insertBefore(StringNode str, char newChar, char beforeChar) { StringNode newNode = new StringNode(newChar, null); // If the string is empty or beforeChar is in the current first node, // return the new node, which is the new first node. if (str == null) { return newNode; } else if (str.ch == beforeChar) { newNode.next = str; return newNode; } StringNode trail = null; StringNode trav = str; while (trav != null) { if (trav.ch == beforeChar) { // Perform the insertion. Given the else-if check above, // we know that trail is non-null if we get here, // so we don't need to worry about a null-pointer exception. trail.next = newNode; newNode.next = trav; // We're done. Return the first node as required. return str; } trail = trav; trav = trav.next; } // If we get here, we didn't find beforeChar, // so we insert the new node at the end of the list // by using trail, which is pointing to the current last node. trail.next = newNode; return str; }