反转LinkedList c ++ [英] Reverse a LinkedList c++

问题描述

可能重复：

无法反转链接列表

m尝试反转链表：

  void LinkedList :: reverseList（）
 {
 Node * next = _head; 
 node * prev = 0; 
 while（next！= 0）
 {
 Node * tmp = next-> _next; 
 next-> _next = prev; 
 prev = next; 
 next = tmp; 
} 
} 
  

> 2-> 1

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

任何帮助？

感谢

解决方案

您的反向函数工作，因为它成功反转列表。这不是问题。您可能有2次调用 print 。一个前后，一个后。在这两种情况下，您注意到传递到 print 的节点是什么？

因为你说你发现了这个问题，

在 reverse 代码中，不要更新 _head ，但是当你 reverse 的列表，头实际上从 4 到 1 。因为你从不更新 _head ，当你第二次调用 print （ / code> call）你开始打印 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; 
} 
} 
  

Possible Duplicate:
Unable to reverse a linked list

I'm trying to reverse a linked list:

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

Lets say the list is: 4->3->2->1

When I print the list, I only see 1 (The print function is good).

Any help?

Thanks

解决方案

Since you said you wanted to find the problem on your own, I'll just give you a hint instead of the solution.

Your reverse function works in that it successfully reverses the list. That isn't the problem. You probably have 2 calls to print. One before and one after the reverse. What do you note about the nodes being passed to print in both cases? What does that tell you?

EDIT:

Since you said you've found the problem, I'll post the actual solution.

In your reverse code, you never update the _head of the list, but when you reverse the list, the head does actually change from 4 to 1. Since you never update _head, when you call print the second time (after the reverse call) you start printing at 1, That being the end of the list, that's the only node printed.

The solution is to update _head when you reverse the list. The simplest way to do this is to simply update it in each iteration. This may be slightly less efficient than other possible solutions, but it doesn't change the time complexity of the algorithm -- it's still 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;
    }
}

这篇关于反转LinkedList c ++的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！