Reverse a LinkedList c++

Question

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

Yes, it's C++, give Node some methods. Let them swap their places in the list without swapping their values. Then find both ends of the list and swap them, working your way along until you either reach the same node at both ends or the ones you've just swapped. — CashCow, Oct 23 '12 at 15:13
It should, really. If you add `_head = prev` after the `while` loop, your code is exactly identical to my answer [here](http://stackoverflow.com/a/4908881/500104). I've also tried and verified it on [LWS](http://liveworkspace.org/code/f42689ac1565bb3f9947076247e624f3). — Xeo, Oct 23 '12 at 15:45
Thank you Xeo, my printList function may cause the problem.. although it prints it good before the reversing. — Maroun, Oct 23 '12 at 16:00
Indeed.. I called it once before and once after the reversing.. (I traveled with _head itself.. that caused the problem) — Maroun, Oct 23 '12 at 16:05

John Dibling · Accepted Answer · 2012-10-23T16:10:11.100

2

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;
    }
}

edited Oct 23 '12 at 16:10

answered Oct 23 '12 at 15:56

John Dibling

99,718
31
186
324

The printList function doesn't receive any parameters, it begins with the _head and then travels until the end of the list (until 0 is the next of the last node).. – Maroun Oct 23 '12 at 16:01
Now I get it.. thank you very much :) – Maroun Oct 23 '12 at 16:02
You're welcome. Do you want me to post the solution now? – John Dibling Oct 23 '12 at 16:04
Sure.. now I fixed it :) I should have "traveled" on a copy of _head and not _head itself on the print function. – Maroun Oct 23 '12 at 16:06
@Maroun: Ouch, that is a bad idea, yeah. :) You would've noticed that if you made your `print` member `const`, though! As in `void print() const{ ... }`. – Xeo Oct 23 '12 at 16:12
Indeed.. 'const' can save a lot of time :) thanks – Maroun Oct 23 '12 at 16:15

Kerrek SB · Answer 2 · 2012-10-23T15:31:35.097

1

Try something like this.

Doubly-linked list:

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

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

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

Singly-linked list:

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

    n->next = prev;

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

edited Oct 23 '12 at 15:31

answered Oct 23 '12 at 15:25

Kerrek SB

464,522
92
875
1,084

My first thought exactly, but it appears to be a single-linked list. – bitmask Oct 23 '12 at 15:27
There's never any mention of `n->prev`. :) – Xeo Oct 23 '12 at 15:27
OK, I made two versions, one for a double and one for a single list. – Kerrek SB Oct 23 '12 at 15:32
I'll try this one.. Can someone explain why my code doesn't work? What I'm missing here? – Maroun Oct 23 '12 at 15:34
@Maroun85: Didn't Xeo already explain it? You never reassign `_head` in your code. – Kerrek SB Oct 23 '12 at 15:40

score 0 · Answer 3 · answered Oct 23 '12 at 15:35

I like recursion; It's easier to grasp and verify;

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;
}

Reverse a LinkedList c++

3 Answers3

Linked

Related