2

可能重复：
无法反转链表

我正在尝试反转链接列表：

void LinkedList::reverseList()
{
    Node *next=_head;
    Node *prev=0;
    while(next!=0)
    {
        Node *tmp=next->_next;
        next->_next=prev;
        prev=next;
        next=tmp;
    }
}

假设列表是：4->3->2->1

当我打印列表时，我只看到 1（打印功能很好）。

有什么帮助吗？

谢谢

4

3 回答 3

2

既然你说你想自己找到问题，我只是给你一个提示而不是解决方案。

您的reverse函数的工作原理是它成功地反转了列表。那不是问题。您可能有 2 次调用print. 一个前一个后一个反向。关于这两种情况下传递给的节点，您有什么注意事项print？这告诉你什么？

编辑：

既然你说你已经找到了问题，我会发布实际的解决方案。

在您的reverse代码中，您永远不会更新_head列表的 ，但是当您reverse列出列表时，头部实际上确实从4变为1。由于您从不更新_head，因此当您print第二次调用时（在reverse调用之后），您开始打印1，这是列表的末尾，这是唯一打印的节点。

_head解决方案是在您反转列表时进行更新。最简单的方法是在每次迭代中简单地更新它。这可能比其他可能的解决方案效率略低，但它不会改变算法的时间复杂度——它仍然是 O(n)：

void LinkedList::reverseList()
{
    Node *next=_head;
    Node *prev=0;
    while(next!=0)
    {
        Node *tmp=next->_next;
        next->_next=prev;
        _head = next;
        prev=next;
        next=tmp;
    }
}
于 2012-10-23T15:56:07.950 回答
1

尝试这样的事情。

双向链表：

for (Node * n = _head, * next; ; n = next)
{
    next = n->next;

    std::swap(n->next, n->prev);

    if (next == NULL) { _head = n; break; }
}

单链表：

for (Node * n = _head, * prev = NULL, * next; ; prev = n, n = next)
{
    next = n->next;

    n->next = prev;

    if (next == NULL) { _head = n; break; }
}
于 2012-10-23T15:25:52.587 回答
0

我喜欢递归；更容易掌握和验证；

Node* LinkedList::reverseList() { // returns tail
  if (!_head || !_head->_next)
      return _head;
  Node* const h = _head;
  _head = _head->_next;
  h->_next = NULL;
  return reverseList()->_next = h;
}
于 2012-10-23T15:35:29.170 回答