Return 倒数第 K 个：输出不正确

Question

我正在研究一种简单的算法，试图从线性链表中找到倒数第 k 个元素但是，在我的解决方案中，它没有输出我期望的正确数字。

我知道如何解决这个问题，但我想知道为什么头部递归没有按我预期的方式工作。如果我能再得到一双眼睛，我将不胜感激。

包装函数

public int findKthToLast(int kth){
        //If zero items in the list
        if(head == null){
            System.out.println("List is empty");
            return 0;
        }
        //If 1 item in the list
        if(head.getNext() == null){
            System.out.println("Only 1 item in the list which is: " + head.getData());
            return 0;
        }
        //Allocating an array of size 1. This will help me keep track on what kth element when I go back from the recursion
        int[] array = new int[1];
        array[0] = -1;

        //the '1' below represents the length. it will increment as you see in the recursive solution
        return findKthToLast(head,kth,1,array);
    }

递归

public int findKthToLast(Node head,int kth,int length, int [] array){
        //if final item in the list
        if(head.getNext() == null){
            //if kth element is greater then total length just return 0
            if(kth >= length){
                return 0;
            }
            //kth = 0 means output the final item in the list. returns head.data
            if(kth == 0){
                return head.getData();
            }
            //when I backtrack from the stack I need to know if the kth to final element is equal to length. That's where the array comes from
            array[0] = length - kth;
            return 0;
        }
        int element;
        element = findKthToLast(head.getNext(),kth,++length,array);
         
        //if equal then I'm done. return the head.data
        if(length == array[0]){
            return head.getData();
        }
        return element;

    }

问题：

在列表中：8 -> 4 -> 2 -> 1。如果 kth = 1（我想要最后一个项目，所以在这种情况下值为“2”）输出应该是“2”。但是，在我当前的代码中，我收到的数字高了 1，因此值“4”

我不想要正确的代码。我知道我是否从

改变了我的基本案例

if(head.getNext() == null)
to 
if(head == null)

那么我的代码就完全可以正常工作了。我想要的是为什么我当前的解决方案不起作用。我是否错误地可视化了调用堆栈？谢谢

Answer 1

您可能比自己聪明，因为在每次递归调用时您使用一种非常不正常的方法来计算列表的长度。您修改了长度变量，以便正确地将增加的长度传递给下一个递归调用，而不是仅将当前长度加一……但是，当您的函数弹出时，您会使用该增加的长度，从而导致您计算错误。

让我们逐步完成以下示例：

8 -> 4 -> 2 -> 1
findKthToLast(8, 1, 1, [-1])
|
|-> 8.next is NOT null
    |
    | element = findKthToLast(4, 1, ++1, [-1])
      |
      | -> 4.next is NOT null
           |
           | element = findKthToLast(2, 1, ++2, [-1])
             |
             | -> 2.next is NOT null
                  |
                  | element = findKthToLast(1, 1, ++3, [-1])
                    |
                    | -> 1.next IS null
                         | kth is NOT 0
                         | => array[0] <- 4 - 1 = 3 (correct)
                         | return 0
                    | element = 0
                    | length is 4 != 3 because of prefix increment (length should be 3 but you incremented before calling the function)
                    | return 0
             | element = 0
             | length is 3 == 3 because of prefix increment, so return current node
             | return 2 (not correct but this is what you told the code to do)
      | element = 2
      | length is 2 != array[0] 
      | return 2
| return 2

就我个人而言，我会选择双指针 slow/fast 方法，但是如果您必须使用递归，那么我会让自己更轻松并保持在后面递增的长度计数器（最后一个元素 returns 0，然后在后续调用中 return element + 1）并将正确的值存储在数组中。

Return 倒数第 K 个：输出不正确

Return Kth to Last: Incorrect output

java

algorithm

linked-list

data-structures

singly-linked-list