Finding the kth to last element of a singly linked list

Question

I have two recursive solutions to the "kth to last element of a singly linked list" problem in Java:

Solution 1:

public static Node nthToLast(Node head, int k , int i){
    if (head == null) return null;
    Node n = nthToLast(head.next, k, i);
    i = i + 1;

    if (i == k) return head;

    return n;
}

Solution 2:

public class IntWrapper {
    public int value = 0;
}
public static Node nthToLast(Node head, int k, IntWrapper i){
    if (head == null) return null;
    Node n = nthToLast(head.next, k, i);
    i.value = i.value + 1;

    if (i.value == k) return head;

    return n;
}

The first solution returns null, while the second solution works perfectly. The first solution passes k by value, while the second solution wraps the int value in a class and passes it.

I have two questions:

1. Why is the first solution not working in Java? Why is pass-by-value through the local variable i in each method call not working the same as the pass-by-reference version?

2. The Integer class in Java wraps int, but replacing the int to Integer in the first solution does not work as well. Why?

Answer 1

In Solution 2, you're using IntWrapper to remember values across recursive invocations. Here, IntWrapper acts like a global value.

If you use local variables such as a primitive integer, you cannot preserve the incremented (i = i + 1) values across invocations. Therefore, the statement if (i == k) return head; never becomes true, unless maybe if k = 1.

Most interestingly, you cannot use Integer because Java wrapper classes are immutable in nature. The moment you do i = i + 1, a new object is created (LHS) and the old one (RHS) is thrown away/garbage collected.

Answer 2

1. The first solution does not work because every time you pass the same value in a i variable. If you move the line i = i + ​​1 over the line Node n = nthToLast (head.next, k, i), everything should work without a problem.
2. Integer class is immutable, so behaves like a normal int. That's why if you use an Integer in the first solution function will not work correctly. You can replace lines of code as I mentioned above that the first solution worked with an Integer.
The second solution works because the way you increment the counter does not overwrite the reference to the counting object.

Answer 3

In your solution 1 you should increment i before calling recursively the method. This version should work:

public static Node nthToLast(Node head, int k , int i) {
    // checks empty case
    if (head == null) { return null; }

     // checks if current node is the solution
    if (i == k) { return head; }

    // else checks next node
    return nthToLast(head.next, k, i+1); 
}