How to read a singly linked list backwards?

Question

One method which I can think of is to reverse the list and then read it. But this involves changing the list which is bad.
OR I can make a copy of the list and then reverse it, but this uses additional O(n) memory. Is there any better method which doesn't use extra memory and doesn't modify the list and runs in O(n) time

reverse linked list code is something like this in c#

Void Reverse (Node head)
{
    Node prev= null;
    Node current = head;
    Node nextNode = null;

     while (current!=null)
     {
      nextNode = current.Next;
      current.Next = prev;
      prev=current;
      current = nextNode; 

     }
     head = prev;

}

Recursive solution is

void ReadBackWard (Node n)
{
    if (n==null)
     return;
    else
     ReadBackward(n.Next);

    Console.WriteLine(n.Data);

}

Answer 1

Well, the naive solution would be to keep track of which node you're currently at, then iterate from the start until you find that node, always saving the node you just left. Then each time you find the node you're currently at, you produce the node you just left, save that node as the one you're currently at, then re-iterate from the start.

This would of course be horribly bad performance-wise.

I'm sure some smarter people have a better solution.

Pseudo-code (with bugs even):

current node = nothing
while current node is not first node
    node = start
    while node is not current node
        previous node = node
        node = next node
    produce previous node
    set current node to previous node

Answer 2

you could read it in O(n^2) -- every time go to the last node read and print out the previous one

Answer 3

Really you should be using a doubly-linked list.

If this isn't possible, I think your best option will be to construct a copy of the list that has been reversed.

Other options, such as relying on recursion (effectively copying the list to the stack) could cause you to run out of stack space if the list is too long.

Answer 4

To use O(n) memory and O(n) performance, create a stack; push everything on as you iterate in the forwards direction, then pop everything off, yielding the results.

To use O(n^2) performance (but O(1) extra memory), read it forwards each time, up the the node before the last one you got to.

Example:

IEnumerable<T> Reverse (Node head) {
    Stack<Node> nodes = new Stack<Node>();
    while(head != null) {
        nodes.Push(head);
        head = head.Next;
    }
    while(nodes.Count > 0) {
        yield return nodes.Pop().Value;
    }
}

Answer 5

If you short of memory you can reverse list, iterate over it and reverse it again. Alternatively you can make a stack of pointers to nodes (or whatever is like a pointer in C#).

Answer 6

One of the hallmarks of a singly-linked list is that it is, in fact, singly linked. It is a one-way street, and there's no way to overcome that unless you turn it into something else (such as a reversed singly-linked list, a stack, a doubly-linked list...). One must be true to the nature of things.

As has been pointed out earlier; if you need to traverse a list both ways; you need to have a doubly-linked list. That is the nature of a doubly linked list, it goes both ways.

Answer 7

This is messy but works:

class SinglyLinkedList {
SinglyLinkedList next;
int pos;
SinglyLinkedList(int pos) {
 this.pos = pos;
}
SinglyLinkedList previous(SinglyLinkedList startNode) {
 if (startNode == this) return null;
 if (startNode.next == this) return startNode;
 else return previous(startNode.next);
}

static int count = 0;
static SinglyLinkedList list;
static SinglyLinkedList head;
static SinglyLinkedList tail;
public static void main (String [] args) {
 init();

 System.out.println("Head: " + head.pos);
 System.out.println("Tail: " + tail.pos);

 list = head;
 System.out.print("List forwards: ");
 while (list != null) {
  System.out.print(list.pos + ",");
  list = list.next;
 }

 list = tail;
 System.out.print("\nList backwards: ");
 while (list.previous(head) != null) {
  System.out.print(list.pos + ",");
  list = list.previous(head);
 }
}
static void init() {
 list = new SinglyLinkedList(0);
 head = list;
 while (count < 100) {
  list.next = new SinglyLinkedList(++count);
  list = list.next;
 }
 tail = list;
}

}

Answer 8

Assuming your singly-linked list implements IEnumerable<T>, you can utilize LINQ's Reverse extension method:

var backwards = singlyLinkedList.Reverse();

You'll need to add a using System.Linq; directive at the top of the code file to use LINQ's extension methods.

Answer 9

A variation of creating a stack and pushing all the elements onto the stack is to use recursion (and the system's built in stack), this is probably not the way to go with production code but serves as a better (IMHO) interview answer for the following reasons:

1. It shows that you grok recursion
2. It's less code and appears more elegant
3. A naive interviewer may not realize that there is a space overhead (if this is the case you may want to consider whether you want to work there).

Answer 10

There is a third solution, this time using O(log(n)) memory and O(n log(n)) time, thus occupying the middle ground between the two solutions in Marc's answer.

It is effectively a reverse in-order descent of a binary tree [O(log(n))], except at each step you need to find the top of the tree [O(n)]:

1. Split the list in two
2. Recurse into the second half of the list
3. Print the value at the midpoint
4. Recurse into the first half

Here is the solution in Python (I don't know C#):

def findMidpoint(head, tail):
  pos, mid = head, head
  while pos is not tail and pos.next is not tail:
    pos, mid = pos.next.next, mid.next
  return mid

def printReversed(head, tail=None):
  if head is not tail:
    mid = findMidpoint(head, tail)
    printReversed(mid.next, tail)
    print mid.value,
    printReversed(head, mid)

This could be recast using iteration instead of recursion, but at the cost of clarity.

For example, for a million-entry list, the three solutions take on the order of:

Solution   Memory       Performance
=========================================
 Marc #1     4MB    1 million operations
  Mine       80B    20 million operations
 Marc #2      4B    1 trillion operations