链表最后N个节点的和

Question

给定的问题是我们必须找到一个链表的最后n个节点的和。如果列表是这样的示例:-

1->2->3->4->5->6->7

， n为3

那么答案应该是18(从5 + 6 + 7)。

这是我的解决方案->

Node*temp = head ; int sum = 0;int cnt = 1;
if(n<=0){
return 0 ;
}
while(cnt!=n)
{
temp = temp->next ;cnt+=1 ; 
}
temp = temp->next ;
while(temp!=NULL)
{
sum+= temp->data ; temp = temp->next ;
}
return sum ;

编辑器给出了一些输入情况的分割转储。我哪里做错了?

Answer 1

您的代码存在一些问题，即1)在第一个while(cnt!=n)中，您没有考虑temp为null时的情况，这会导致您这样做时出现问题:

temp = temp->next

此外，你想对最后的n个元素求和，但实际上你是在尝试对前n个元素之后的元素求和。

这个问题使用递归更容易解决，就像我们在这里看到的那样。在迭代中，一种方法是计算列表中的元素数量，然后在找到第total elements - 'n'个元素后开始对元素求和。

if(n<=0){
return 0;
}
// Let us calculate how many elements are on the list.
Node *temp = head; 
int total_elements = 0;
while(temp != null)
{
total_elements++;
temp = temp -> next;
}
int n_th = total_elements - n;
if(n_th < 0) return 0;

temp = head;
int cnt = 0;
// Here we do need to check temp for null 
// because we know temp has at least n_th elements
while(cnt != n_th)
{
cnt++;
temp = temp->next;
}
temp = temp->next ;
int sum = 0;
while(temp != NULL)
{
sum += temp->data ; 
temp = temp->next ;
}
return sum ;

另一种方法是，在计算列表中的元素数时，对所有元素求和，然后最后减去不属于和的(初始)元素:

if(n<=0){
return 0;
}
// Let us calculate how many elements are on the list.
Node *temp = head; 
int total_elements = 0;
int sum = 0;
while(temp != null)
{
total_elements++;
sum += temp->data;
temp = temp -> next;
}
int n_th = total_elements - n;
if(n_th < 0) return 0;

temp = head;
int cnt = 0;
while(cnt != n_th)
{
cnt++;
sum -= temp->data;
temp = temp->next;
}
return sum ;

Answer 2

一个可能发生分割错误的例子是当n等于链表的长度时

在你的例子中，如果我们设置n为7,temp指针将在while循环中被转发7次。所以，它到达链表的末端。现在，如果你在链表的末尾执行temp = temp->next ;，那么你就会出现分割错误，因为链表中没有下一个元素。

这个问题的一个简单/天真的解决方案是:

1. 计算列表中元素的总数
2. 从n中减去它以获得最初必须忽略的元素数量。
3. 总结其余元素。

当然可以有其他更好的方法来解决这个问题。

Answer 3

你的问题是这个循环

while(cnt!=n)
{
temp = temp->next ;cnt+=1 ; 
}

您将temp增加n次。但是您甚至没有检查temp是否指向有效条目。是不是NULL

其次，逻辑是错误的。您正在跳过第一个n数字并计算剩余数字的总和。你应该做的是得到总数，然后迭代上面提到的while循环，直到total_num - n次。然后对剩下的数求和。