时间戳

首页 > 解决方案 > 有关问题：查找链表的最后 N 个节点的总和

java - 有关问题：查找链表的最后 N 个节点的总和

问题描述

我正在解决这个问题，实际上我确实完成了它。但是，我仍然想增强我的解决方案。是否有另一种方法来解决这个问题，从而降低时间复杂度？我的解决方案的时间复杂度是 O(n^2)。此外，我考虑了一种递归解决它的方法，但最后我将两者混合在一起；因为我将遍历“迭代”以获取numOfNodes然后遍历“递归”以计算最后一个节点。我还没有实现它，但我对那个解决方案感到困惑，我不知道它是否正确！

**请先看代码 ,,,,,,,,,,,,,,,,,,,,,, 思路是numOfNodes在列表中计数到，然后再过来遍历但是对于每个节点，我会减少numOfNodes. 而当 时numOfNodes == k，则使用 for 循环计算总和。

这是代码：

public int sum(Node head, int k){
      int sum = 0;
      int numOfNodes = 0;


      Node temp = new Node(0);
      temp = head;
      

      while(temp != null){
          numOfNodes++;
          temp = temp.next;
      }
      
      temp = head;
      
      while(temp != null){
          if(numOfNodes == k){
            for(int i = 0; i<k; i++){
                sum += temp.data;
                temp = temp.next;
            }
          }else{
            numOfNodes--;
            temp = temp.next;
          }
      }
      
      return sum;
    }

先感谢您！

标签： javaalgorithmdata-structureslinked-listnodes

解决方案

您的代码对列表中的节点数持乐观态度。当列表少于k节点时，它将返回 0。我认为在这种情况下应该返回所有节点的总和。

至于算法的其余部分：很好。它使用恒定的辅助存储器并以线性时间运行。它不是你想象的二次方：虽然你在列表中循环了第二次，但这只会使迭代次数为 O(2n)，仍然是 O(n)。

您还可以通过跟踪滞后k于前导节点引用的节点的第二个节点引用，将两个迭代合并为一个。

这是看起来的样子：

public static int sum(Node head, int k){
    int total = 0;
    Node lag = head;
    Node lead = head;
    while (lead != null) {
        if (--k < 0) {
            total -= lag.data;
            lag = lag.next;
        }
        total += lead.data;
        lead = lead.next;
    }
    return total;
}

递归解决方案的缺点是需要 O(k) 堆栈空间。

推荐阅读