破解编程面试，第6版- Q: 2.2

Question

问题是返回单链表的第k到最后一个元素。所有提出的解决方案都很复杂，我不知道为什么我的解决方案无效。有人能告诉我为什么吗?

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

单链表不会同时包含next和previous。你有一个双重链表，这显然使这个问题更容易。

Answer 2

我没有那本书的副本，所以我不知道里面可能会有什么复杂的解决方案，但是下面的两指解决方案对我来说似乎很简单，除了使用单链表之外，与您的解决方案没有什么不同:

/* 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;
}

Answer 3

书中的第一个解决方案是:

解决方案#1:如果链表大小已知

如果链表的长度已知，那么倒数第k个元素就是(长度- k)个元素。我们可以只需遍历链表来找到这个元素。因为这个解很简单，我们几乎可以这肯定不是面试官想要的。

但是我们可以很容易地找到链表的大小通过一次!所以修改OP的问题，我问下面的答案有什么问题?

使用两个指针。其中一个用于查找链表的大小，另一个用于(size - k)步长。

(Python实现)

def kth_to_last(head, k):
    p1 = head
    p2 = head
    counter = 0
    while p1.nxt is not None:   # calculating the size of the linked list
        p1 = p1.nxt
        counter += 1
    for _ in range(counter - k):
        p2 = p2.nxt
    return p2.val