[ACCEPTED]-How to read a singly linked list backwards?-singly-linked-list

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

To use O(n^2) performance 3 (but O(1) extra memory), read it forwards 2 each time, up the the node before the last 1 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;
    }
}

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

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

Really you should be using a doubly-linked 7 list.

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

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

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

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

It is effectively a reverse in-order 8 descent of a binary tree [O(log(n))], except at each 7 step you need to find the top of the tree 6 [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 5 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 4 instead of recursion, but at the cost of 3 clarity.

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

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

void reverse_print(node *head) 
{
    node *newHead = NULL, *cur = head;

    if(!head) return;

    // Reverse the link list O(n) time O(1) space
    while(cur){
        head = head->next;
        cur->next = newHead;
        newHead = cur;
        cur = head;
    }

    // Print the list O(n) time O(1) space
    cur = newHead;
    while(cur) {
        printf(" %d", cur->val);
        cur = cur->next;
    }

    // Reverse the link list again O(n) time O(1) space
    cur = newHead;
    while(cur){
        newHead = newHead->next;
        cur->next = head;
        head = cur;
        cur = newHead;
    }
    // Total complexity O(n) time O(1) space
}

0

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

var backwards = singlyLinkedList.Reverse();

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

A variation of creating a stack and pushing 5 all the elements onto the stack is to use 4 recursion (and the system's built in stack), this 3 is probably not the way to go with production 2 code but serves as a better (IMHO) interview 1 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).

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

This would of 3 course be horribly bad performance-wise.

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

Pseudo-code 1 (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

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

}

0

If in the Explicit Stack program, we create 5 a stack for just the data of each node (instead 4 of creating the Stack of type <Node>, we create 3 Stack of type <T>) wouldn't it be even better? Because 2 we don't need to store any other information 1 of the Node then.

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