高效地从链表中的最后一个元素中找到第nth

什么是从单/双向链表中的最后一个元素中找到第nth的有效方法？高效地从链表中的最后一个元素中找到第nth

2016-11-21 Divij Sehgal

这似乎毫无意义，没有办法比平凡的方式做得更好。 – harold

下面是从链表中最后一个元素中找到第n个元素的有效方法。

struct Node{ 
    int data; 
    struct Node *next; 
}; 

int getNthFromLast(struct Node *head, int n){ 
    struct Node *curr = head; 
    struct Node *nthFromLast=NULL; 
    int count=0; 
    int value=-1; 
    while(curr!=NULL){ 
     count++; 
     curr=curr->next; 
     if(count==n){ 
      nthFromLast=head; 
     }else 
      if(count>n){ 
       nthFromLast=nthFromLast->next; 
      } 
    } 
    if(count>=n){ 
     value=nthFromLast->data; 
    } 
    return value; 
}

这个例子是用C++编写的，可以在其他语言中进行类似的复制。该方法传递一个指向链表的第一个节点的指针，以及最后一个元素的索引，该元素返回其数据。如果该位置不存在，则该方法返回-1。

在双向链表和圆形链表的情况下也可以采用类似的方法。

编辑：如果是双向链表，只需将n项反向移动即可。完全忘记了这一点。积分：Jim Mischel

来源

2016-11-21 16:01:33

有了一个双向链表，你所要做的就是从末尾向后计数'n'个节点。还要注意的是，这并没有比完全扫描列表来查找计数，然后重新开始并向前移动（（count -n））次数那么有效。 –

同意双向链接列表点，忘记考虑这一点。感谢您强调这一点。将编辑。虽然，如果你首先发现count（'loop 1）'，然后向前移动'（count -n）'，那么你是不是会徒劳地执行'（count - n）'长度的第二个循环？如果说n的值在较小的一边，那么你实际上必须遍历列表的一半以上而没有任何有意义的增益。所以我想这就是第二个指针进入的地方，它追踪'（count-n）'项的位置。 –

是的，但如果你用两遍来做，你只会在循环中增加一个指针。在你的版本中，你最终在一次通过中执行'count +（count-n）'指针增量。在两遍版本中，你一次执行'计数'增量，第二次执行'（计数 - n）'增量。所做的工作量是相同的。 –

实际上，链接列表并不是用于这种目的的最佳数据结构（如通过索引查找指定元素）。当然，你可以使用一些小技巧，比如存储桶列表（限制大小的列表）和从两端搜索元素。它可能会增加一点点的发现，但不会那么有效（平均复杂度将保持O（N））而且它将会结构复杂。我认为任何方法都会导致创建指定类型的类型（如数组或字典）。如果元素访问的复杂性很关键，那么阵列的使用可能会有所帮助？如果您经常在列表末尾添加元素，则可以使用数组，并按分摊的容量增加。

来源

2016-11-21 20:39:56 LmTinyToon

具体询问如何在链表中找到第n个元素*的问题，而不是找出某些未指定集合中第n个元素的最有效方法。这个假设是OP有一个现有的链表。将它转换为数组或任何其他“更高效”的数据结构无论如何都需要O（n）个时间。现在，如果他需要执行多次倒数第n次计算，那么可能会更好地产生O（ n）一次性成本，以便后续查询可以在O（1）时间内完成 –

只有在这种情况下，你的算法t才是好的，在这种情况下，列表将保持不变（在创建临时数组之后）。不是那么有效。 – LmTinyToon

高效地从链表中的最后一个元素中找到第nth

回答

相关问题