获取链接列表中给定节点地址的节点的地址

因此，我非常了解遍历链表以及获取列表中的下一个节点。现在我试图走向另一个方向，但我很快意识到它并不像看起来那么容易。与可以向前和向后迭代的数组不同。我似乎被难住了。获取链接列表中给定节点地址的节点的地址

因此，如果我有1 - > 2 - > 3 - > 4 - > NULL的列表我将如何获得节点2给定节点3的位置的地址？

我开始搞乱下面的代码，它返回到节点3的所有项目。我只是不明白我如何得到前一个节点？顺便说一句searchList()返回一个节点的地址，如果你给它的节点 - >数据值。使用上面的列表searchList(3)将返回具有3作为其数据成员的节点的地址。

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

void llclass::getPrevious() { 
    node *stop = searchList(nodeItem), 
     *start = head; 

    while (start != stop) { 
     cout << start->data << endl; 
     start = start->next; 
    } 
}

来源

2014-03-26 MrPilot

听起来就像你想得到一个节点的前一个节点，其值是作为输入给你的。这应该为你做到这一点：

node* llclass::getPrevious(int item) 
{ 
    node* previous = NULL; 
    node* current = head; 
    while(current) 
    { 
     if (current->data == item) 
     { 
      return previous; 
     } 
     else 
     { 
      previous = current; 
      current = current->next; 
     } 
    } 
    return NULL; 
}

来源

2014-03-26 03:13:55 DigitalEye

非常感谢你这是我正在努力完成的。有一件事你为什么最后返回NULL？ – MrPilot

如果您要查找的项目不在列表中，那么您没有有效的前一个节点返回给调用者。为了通知这个场景的调用代码，我选择返回NULL。 – DigitalEye

像你这样一个单向链表，则无法获得节点2的地址，如果你只给节点3的地址，你将不得不在头节点和迭代开始直到达到3，跟踪前一个节点（在这种情况下为2）。或者，您可以使用包含“node * previous”的双向链表会员。

来源

2014-03-26 02:25:55

对于这个问题，使用双向链表仍然只会产生一个O（n）算法，更不用说有n个额外的指针的成本！ – DigitalEye

确实，给定了新的信息，但是他说他给了节点3的位置，我假定它指的是节点3的地址。如果是这种情况，双向链表将使O（1）“算法” （即，只解引用'以前的'指针）。 –

获取链接列表中给定节点地址的节点的地址

回答

相关问题