Reverse-printing single-linked list

Question

Anybody knows how to print single-linked list in reverse order (one pass and a fixed and independent of the number of elements RAM).

Answer 1

My answer. There is no answer that solves this to your specs. It can't be multi-pass, it cant be recursive (which I think is considered single), it has to be constant memory...

I dont think you will discover a solution, and the people who said you could do it obviously have some form of a trick aspect to the question. They aren't obviously using the same set of definitions that this community is using.

Answer 2

I think you can do that in O(n) time and O(1) space, but technically it's not "one pass".

1. reverse the linked-list: O(n)
2. print: O(n)
3. reverse the linked-list back: O(n)

Answer 3

The this option assumes that you know the count (if not that's one pass gone already), or failing that if you must use one pass, then just set count to some reasonable large maximum upper limit value.

long count = 10000; // set this to whatever the count is, or calcualte it
string filename = @"c:\foo.out";
using (StreamWriter writer = new StreamWriter(filename))
{
    int index = 0;
    long maxLength = 12; // set this to the max length of an item + 2 (for /r/n)
    while(values.Next())
    {
        writer.BaseStream.Seek(maxLength * (count - index - 1), SeekOrigin.Begin);
        writer.WriteLine(values[index].ToString().PadLeft(maxLength));
        writer.Flush();
        index++;
    }
}

The output will be in the c:\foo.out file, padded by spaces. Since the question did not state where you need to output, or what format the output should be in (such as not include blanks lines beforehand). Given it's a linked list the length could be very large (>int.MaxValue), such that writing output to a file is quite a reasonable transport format.

This answer meets both O(n) write performance (and indeed one pass), while also using no additional memory than the output stream which is always going to have to be O(n) because how else will you fit them all on the screen..

A response to this answer would be that you can't seek backwards in the output stream, then just print a \r return character and seek backwards that way, failing that reply to the interviewer asking if identifying or meeting impossible requirements are part of the job description.

Answer 4

String s ="";
for(each element el in list)
     s=el.data+", "+s;
 println(s);

This is one pass.

Answer 5

Here is a solution with the java.util.LinkedList The memory stays the same since you remove and add the element to the same list. I think is reasonable to assume any decent implementation of a singly linked list will keep track of its size, head and tail.

import java.util.Arrays;
import java.util.LinkedList;

class PrintReverse {
    public static void main(String[] args) {
        Integer[] array = {1, 2, 3, 4};
        LinkedList<Integer> list = new LinkedList<Integer>(Arrays.asList(array));
        System.out.println(list);
        printListBackward(list);
    }

    public static void printListBackward(LinkedList<Integer> list) {
        int size = list.size();

        for (int i = 0; i < size; i++) {
            Integer n = list.removeLast();
            list.push(n);
            System.out.println(n.toString());
        }
        System.out.println(list);

    }
}

Which produces the following output...

[1, 2, 3, 4]
4
3
2
1
[1, 2, 3, 4]

What do you think?

Answer 6

Well, you didn't say that it had to be efficient. (Plus there probably isn't a constant memory implementation that's more efficient.) Also, as commenters have pointed out, this is one-pass only when length(list) == 1.

void printReversedLinkedList(listptr root) {
    listptr lastPrinted = null;
    while (lastPrinted != root) {
        listptr ptr = root;  // start from the beginning of the list
        // follow until next is EoL or already printed
        while (ptr->next != null && ptr->next != lastPrinted)
            ptr = ptr->next;
        // print current node & update last printed
        printf("%s", ptr->data);
        lastPrinted = ptr;
    }

Constant memory, O(n^2) efficiency.

Answer 7

void printList(listItem node) {
    if (node.next != null) {
        printList(node.next);
    }

    echoOrSystemOutPrintlnOrPrintfOrWhatever(node.data);
}

printList(rootNode);

Answer 8

Import to an array, print array in reverse order.

Answer 9

Go through the singly linked list and push each item onto a stack. Pop the stack until it is empty, while printing out each element that is popped.

node  = head of node list
stack = new Stack()

while ( node is not NULL )
{
    stack.push( node.data )
    node = node.next
}

while ( !stack.empty() )
{
    print( stack.pop() )
}

Answer 10

I am really wondering how a singly linked list can be traversed reverse.