Printing out elements of a linked list in reverse

user_595559 0
Viewed 455

I am practicing my data structures and trying out this problem on HackerRank on printing the element of a linked list in reverse order.

I have looked through my solutions multiple times but I don't understand why it is wrong.

My Solution:

    static void reversePrint(SinglyLinkedListNode head) {
        if (head==null){
            return;
        }

        ArrayList<Integer> intList = new ArrayList<>();

        while(head!=null){
            intList.add(head.data);
            head = head.next;
        }

         Collections.sort(intList, Collections.reverseOrder());
        for(int i: intList){
            System.out.println(i);
        }
    }

Appreciate if someone can assist on pointing out my mistakes.

singly-linked-list java
2 Answers

Use Stack rather than ArrayList

static void reversePrint(SinglyLinkedListNode head) {
    if (head==null){
        return;
    }

    Deque<Object> intList = new ArrayDeque<>();
    while(head!=null){
        intList.push(head.data);
        head = head.next;
    }

    while(!intList.isEmpty()){
        System.out.println(intList.pop());
    }
}
user_35828310

Appreciate if someone can assist on pointing out my mistakes

The Problem

You used an ArrayList whose behavior is First In First Out, so the order of the elements printed when you for-loop the intList is the same as the order in the linked list, starting from head.

Possible solutions

To fix your approach, you could simply:

1- Insert each element always in the position zero of intList using List#add(int index, E element):

// ...
intList.add(0, head.data);
// ...

2- Or, you can replace the data structure you used to "revert" the elements.

For example, you can use any of the Last In First Out data structures, such as Queue or Deque in their LIFO variant.

Another alternative

Giving you another completely different solution, you could implement it in a recursive manner like this:

static void reversePrint(SinglyLinkedListNode head) {
    if (head != null) {
        reversePrint(head.next);
        System.out.println(head.data);
    }
}

If head is null, do not print anything. Otherwise, first reversePrint the next element and after that, the current one (head.data)... this will cause the reversal effect.

It's worth noting that this doesn't reverse the order of elements, that is, it doesn't modify the next of each element.

user_56406490
Related