CODEWITHSUNDEEP
java
Pervy Sage
Pervy Sage

Reputation: 871

Finding K-th to last element of a singly linked list

I am currently reading the book "Crack the Coding Interview" (5th edition). There is a particular problem in it saying Implement an algorithm to find kth to last element of a singly linked list. There are various approaches discussed to the problem. I am particularly confused by the recursive solution. It goes as follows (shamelessly copying it from the book):

public class IntWrapper {
    public int value = 0;
}

LinkedListNode nthToLastR2(LinkedListNode head, int k, IntWrapper i){
    if(head == null){
        return null;
    }
    LinkedListNode node = nthToLastR2(head.next, k, i);
    i.value = i.value + 1;
    if(i.value == k) {      // We've found the kth element
        return head;
    }
    return node;
}

My question is: We are returning a LinkedListNode when we find that particular node and we are returning a LinkedListNode even when we don't find that particular node. So there is no means to tell kth node from any other node. Can anyone please tell me if my observation is correct or not? If yes, how can we make it correct (other than, of course doing a System.out.println before the return head because that would be just printing the node and not returning it) ?

Upvotes: 3

Views: 1528

Answers (3)

toto2
toto2

Reputation: 5326

I'm not sure that the book you are using is that good. They access member variables without getters/setters. You would see that 15 years ago in Java, but it's a big no-no now. They are in their 5th edition (2011), but it seems they were lazy in did not update their examples as the Java conventions were evolving.

Their recursive solution is quite complicated. I wrote a alternate recursive solution below. It keeps a queue of the latest visited nodes. That queue is kept as small as possible. I am using Java 8's Optional where a returned empty value signifies that the list is too short.

   Optional<LinkedListNode> recur(
                              LinkedListNode currentNode, 
                              int nFromLast, 
                              Queue<LinkedListNode> latestNodes) {

        if (currentNode == null) { // went past the last node
            if (latestNodes.size() > nFromLast)
                return Optional.of(latestNodes.remove());
            else // the queue is too short
                return Optional.empty();
        } else {             
            if (latestNodes.size() == (nFromLast + 1))
                latestNodes.remove();
            latestNodes.add(currentNode);
            return recur(currentNode.getNext(), nFromLast, latestNodes);
        }
    }

It is called initially with an empty queue:

recur(list, k, new ArrayDeque())

[Warning: this paragraph below is at an advanced level.]

It might seem that my solution wastes memory by keeping the queue, but their solution keeps items in memory on the stack. My solution is tail recursive and theirs is not. Unfortunately, it is not an advantage for the time being since the JVM does not optimize for tail recursion. The JVM also keeps everything (including all copies of the queue) on the stack for my method. At least I think my solution is simpler.

Upvotes: 0

Trudbert
Trudbert

Reputation: 3198

Short answer: Your observation is incorrect, the example works as is. To the expanation first simple recusion example:

Factorials: n! = n*(n-1)*(n-2)...*1

Recursive Function:

int fact(int n) {
    if (n==1) {
       return 1;
    } else {
       return n*fact(n-1);
    }
}

So basically the function calls itself until it comes to the point where n==1 and then you get a result after the result has come through to the one you called. So basically 

fact(3) = 3*fact(2) = 3*2*fact(1) = 3*2*1

The same happens in your example:

It starts by running through the list till the end by calling itself with the next element of the list 

LinkedListNode node = nthToLastR2(head.next, k, i);

when it reaches the last node it starts returning stuff

if(head == null){
    return null;
}

only then does the last one before that call go to the line

i.value = i.value + 1;

and starts counting from the last node.

Then checks if it has the kth node from the last by checking

if(i.value == k) {

and if it has it return the head it got.

If it hasn't it return the one it got returned from the one before. For example k=4 and seven node

 head: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null 
                                           | returning
    i= 7    6    5    4   3    2    1      v
       3 <- 3 <- 3 <- 3 <-.-null<- null <- null

Each step is an independent evaluation of the same function knowing not who called it and waiting for the one it called to return something.

Upvotes: 2

Nate
Nate

Reputation: 2492

The trick in this recursive function is that the recursive call happens first - this means that by the time any of the code after the call executes, we'll already be at the last node. Once we get to the end, our function will return null because there is nothing left (head is now null). The final function of our callstack returns null, which means that node = null. Now the function checks to see if the current node is the k-th one (using the accumulator i).

There are two possible cases:

  1. We aren't at the correct node: Our function simply returns node, which as we recall is null. Thus for the next higher function in the callstack, things look just like if it had hit the end, except that i is larger.

  2. We are at the correct node: We return head, not node (remember node = null). In this case, we propagate back up the callstack again, but this time instead of node being null at each layer, it's head, which is the node we want. Eventually we get back to the top, and return the correct element.

So, simply put, the function keeps returning null until we find the element, then it keeps returning the element.

Poorly drawn mspaint picture:

recursive case

Upvotes: 3

Related Questions