CODEWITHSUNDEEP
algorithmdata-structureslinked-list
Andrew K.
Andrew K.

Reputation: 47

Reverse-printing single-linked list

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

Upvotes: 2

Views: 6834

Answers (10)

Luis M.
Luis M.

Reputation: 11

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?

Upvotes: 1

Seph
Seph

Reputation: 8703

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.

Upvotes: 3

Kishor Kundan
Kishor Kundan

Reputation: 3165

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

Upvotes: 0

Ashwin Nanjappa
Ashwin Nanjappa

Reputation: 78528

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() )
}

Upvotes: 0

kasavbere
kasavbere

Reputation: 6003

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

This is one pass.

Upvotes: 2

Peter
Peter

Reputation: 1

Import to an array, print array in reverse order.

Upvotes: 0

StanleyZ
StanleyZ

Reputation: 607

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)

Upvotes: 4

Pedery
Pedery

Reputation: 3636

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

    echoOrSystemOutPrintlnOrPrintfOrWhatever(node.data);
}

printList(rootNode);

Upvotes: 0

jdi
jdi

Reputation: 92617

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.

Upvotes: 10

blahdiblah
blahdiblah

Reputation: 34031

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.

Upvotes: 0

Related Questions