Cracking the Coding Interview, 6th Edition- Q: 2.2

Question

The question is return the kth to last element of a singly linked list. All the proposed solutions are pretty complex, and I don't know why my solution is invalid. Could someone please let me know why?

public class CrackTheInterview {


    /**
     * @param args the command line arguments
     */

    public static Node kthToLast(Node n, int k) //pass in LinkedList's head node
    {
        int counter = 1;
        while (n.next != null)
        {
            n = n.next;


        }
        //at the end of the while loop, n equals the last node in the LinkedList
        while (counter != k)
        {
            n = n.previous;
            counter++;
        }
        //now node n is the kth node from the end

        return n;
    }
}

---

class Node
{
    Node next = null;
    Node previous = null;
    int data;

    public Node (int d)
    {
        this.data = d;
    }

}

Answer 1

A singly linked list would not have both next and previous. You have a doubly linked list, which clearly makes this problem easier.

Answer 2

I don't have a copy of that book, so I don't know what complicated solutions might be found in it, but the following two-finger solution seems pretty simple to me, and is not that different from yours aside from using a singly-linked list:

/* Returns the kth last node in the list starting at n.
 * If the list is empty (n == null) returns null.
 * If k is <= 1, returns the last node.
 * If k is >= the number of nodes in the list, returns the first node.
 */
public static Node kthToLast(Node n, int k) {
    Node advance = n;
    while (--k > 0 && advance != null) {
        advance = advance.next;
    }
    /* Now advance is k nodes forward of n. Step both in parallel. */
    while (advance != null) {
        advance = advance.next;
        n = n.next;
    }
    return n;
}