有关问题：求链表的最后 N 个节点的总和

Question

我正在解决这个问题，实际上我已经完成了。但是，我仍然想增强我的解决方案。是否有另一种方法可以解决此问题，从而降低时间复杂度？我的解决方案的时间复杂度是 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;
    }

提前致谢！

Answer 1

可以在 O(N) 时间和 O(1) Space 复杂度内轻松完成。
这个想法是迭代列表一次并计算列表中的节点数。让列表的大小为 size.
现在再次迭代列表并跟踪访问过的节点。如果 i 在所需范围内（最后 k 个节点），则将这些节点的值添加到结果 sum.

int i=1;
int sum = 0;
Node pointer = head;
while (pointer != null)
{
    if ((size-k) <= i)
    {
        sum += pointer.data;
    }
    i++;
    pointer = pointer.next;
}

Answer 2

假设您希望保持 space 复杂度常数 O(1)，您的解决方案看起来是最优的。我还假设它是一个单链表。

顺便说一句，你的解决方案的时间复杂度不是 O(n^2)。它开着）。您正在进行一次遍历以获得总计数。即 O(n)。您正在进行另一次遍历以获取 k 个节点数。这是两个独立的遍历。所以时间复杂度是 n + n = 2n 或 O(n)。没有内部循环，因此您的解决方案的时间复杂度为 O(n)。

Answer 3

您的迭代解决方案看起来不错，但我建议将您的实际计数代码简化为如下内容：

Node temp = head;
for(int i=0; i<numOfNodes-k; i++) 
    temp = temp.next;

// temp now points to the first node to be counted

int sum = 0;
for(int i=0; i<k; i++) 
{
    sum += temp.data;
    temp = temp.next;
}
return sum;

你提到的递归解决方案的优点是只需遍历列表一次，在返回的路上计算顶部 k 节点。请注意，我们必须使用一个参考值（我使用的是一个简单的单元素数组）来保存计算出的限制，超过该限制我们应该对节点进行计数。

static int sumr(Node node, int pos, int k, int[] lim)
{
    if(node == null)
    {
        // pos now holds the length of the list
        lim[0] = pos-k;
        return 0;
    }
    
    int sum = sumr(node.next, pos+1, k, lim);
    if(pos >= lim[0]) sum += node.data;
    return sum;
}

调用方式：

int sum = sumr(head, 0, 3, new int[1]);

Answer 4

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

至于算法的其余部分：没问题。它使用恒定的辅助存储器并以线性时间运行。它不像你想的那样是二次方的：虽然你第二次循环遍历列表，但这只是使迭代次数 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) 堆栈 space。

有关问题：求链表的最后 N 个节点的总和

Questions Regarding : Find the Sum of Last N nodes of the Linked List

java

algorithm

linked-list

nodes

data-structures