破解编码面试，第 6 版 - Q：2.2

Question

问题是 return 单向链表的倒数第 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

书中第一个解说：

Solution #1: If linked list size is known

If the size of the linked list is known, then the kth to last element is the (length - k)th element. We can just iterate through the linked list to find this element. Because this solution is so trivial, we can almost be sure that this is not what the interviewer intended.

但是我们可以很容易地通过一次就找到链表的大小！所以修改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

破解编码面试，第 6 版 - Q：2.2

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

java

algorithm

linked-list