0

I'm guessing this question is due to my lack of knowledge in data structures, but the question is how to reverse a singly linked list? I was under the impression that using the "previous" field or property to solve this problem would make the singly linked list a doubly linked list, but all of the solutions I have found online involve the use of a previous property. What am I missing here?

bman
  • 80
  • 1
  • 10
  • 2
    you could create a stack, push each item onto the stack in order, then pop each item off of the stack. Of course, that's assuming you know how stacks work. If this is an interview question then the point is for you to explain how you would do it. If you don't know then you don't know; asking strangers on the internet is cheating :) – D Stanley Oct 08 '19 at 20:43
  • itsme86 that example use "prevnode" doesn't that make it a doubly linked list? – bman Oct 08 '19 at 20:52
  • and D Stanley, wouldn't using a stack be cheating since that is using a separate data structure to reverse the list? – bman Oct 08 '19 at 20:54
  • 3
    @bman There is nothing in your question that prohibits the use of a separate data structure. Also the "prevnode" is a local variable, not a property or field of the node elements, that does not make it a double linked list. – GvS Oct 08 '19 at 20:58
  • 1
    @bman: *Implement the stack as a linked list*, and then you're done without using a separate data structure. So, exercise: can you implement a stack as a linked list? – Eric Lippert Oct 08 '19 at 23:57
  • Possible duplicate of [Reversing single linked list in C#](https://stackoverflow.com/questions/8686168/reversing-single-linked-list-in-c-sharp) –  Oct 09 '19 at 02:06

2 Answers2

1

You can just rebuild the list by traversing it. The first element you "pop" out will be the last one in the result, in pseudocode

new_list = nothing
while p != nothing:
    next = p.next
    p.next = new_list
    new_list = p
    p = next
6502
  • 112,025
  • 15
  • 165
  • 265
1

Given that a typical node in a singly-linked list looks something like:

class Node
{
    Node Next {get; set;}
    int Data {get; set;}
}

One helpful thing to do when trying to reverse a list of these is picture how you would do it "by hand". For example, say you have this list:

[head] 9 --> 3 --> 5 --> 1 --> 7 --> [null]

You would want to do something like

[null] <-- 9 <-- 3 <-- 5 <-- 1 <-- 7 [head]

If we walk the list from head to tail, we would start with a temporary "previous" node set to null (representing the last node) and a "current" node set to head, and then simply capture the current node's "next" node in a variable (for later), point the current item's next property to the "previous" node, then set our "previous" node to the current node and the current node to the current node's original next node.

In other words:

Node previous = null;
Node current = head;

while (current != null)
{
    Node next = current.Next;  // capture the next node so we can change it 
    current.Next = previous;   // point this node's next to the previous node
    previous = current;        // update variable for next iteration
    current = next;            // update variable for next iteration
}

head = previous;               // finally we can update the head pointer
Rufus L
  • 36,127
  • 5
  • 30
  • 43
  • So, the Node previous would not make this a doubly linked list? I was under the impression using a previous node would. – bman Oct 09 '19 at 00:01
  • 1
    No, a doubly-linked list has a `Node` class with both a `Next` and a `Previous` property (the nodes in this list are based on the `Node` class at the top of the answer, which only has a `Next` property). The `Node previous` variable is just for storing the last node examined in the loop. It's also not part of the list at all. – Rufus L Oct 09 '19 at 00:03
  • Ah, thank you sir. That is why I was confused. – bman Oct 09 '19 at 00:06