Redirecting to
NADOS


  Prev   Next

Display Reverse Recursive







Self-reverence, self-knowledge, self control - these three alone lead to power.
~ Alfred, Lord Tennyson

Display Reverse Recursive

Welcome back readers!

We hope that you are enjoying your linked list journey so far. Isn't it fun to use a linked list? Indeed it is. We are sure that you like it.

In this article, we will be moving on to the next question that is "Display Reverse Recursive" as it is quite clear from the name that we need to display a linked list in reverse order using recursion.

You need to make sure that the Linked List remains the same in order.

Important Links : Question Video, Solution Video

Before moving any further it's highly recommended that you think about various ways to solve this and give this problem a fair try.

Let's jump to the problem!

Problem Discussion :

In the problem you are given a partially written LinkedList class.

Your job is to complete the body of displayReverse and displayReverseHelper functions. The function is expected to print in reverse the linked list without actually reversing it.

Input and Output is managed for you.

Note -> The online judge can't force you to write a recursive function. But that is what the expectation is, the intention is to help you learn.

If you are facing difficulty in understanding this problem, then I advise you to watch the question video of this problem.

Approach :

Do you remember how recursion works? Well, then it is a very easy problem for you.

Now, in displayReverseHelper, if you look at the signature then you will find that a variable node of type Node is passed as parameter.

We use this function as our hidden function and code our main logic in this one.

We need to reach to the tail of the linked list so that while returning we can print the data of the present node, which gives us the elements of the Linked List in reverse order. So we simply make a call to displayReverseHelper(node.next) which takes us to the next node. This process will keep happening; means as soon as a call is made to node.next it will further make a call to node.next.next and so on.

img

There will come a point in Linked List when this call will be finally made to the tail of the Linked List. And then it will further make a call to its next which points to null, but we need to stop at tail only.

So in order to achieve so, we simply add a base case to the above code.

img

Yes! That looks complete.

But when a user uses this function in main, they don't know that they need to pass the head as an argument while calling the function displayReverseHelper(Node n).

This is where the use of second function displayRevrse() comes into action. In displayReverse(), we make a call to displayReverseHelper(head).

This is also the reason that displayReverseHelper() is a private function whereas displayReverse() is public so that users can only access the displayReverse().

img

Yes! That looks complete.

Let's consider a linked list of size 4 and its elements as: a b c d and look into the stack when displayReverse() is called.

img

What do you think will happen then?

Yes, a call to displayReverseHelper(head) will be made. That means that it will be added to stack, let's represent this call with the address of head in the stack.

Head will further make a call to the next element at 20k. And that to 30k and that to 40k. Now to notice, at 40k it is our last element that is the tail of the linked list.

img

When a further call will be made then the base case will hit.

img
img

After the base case is hit then functions start returning.

At first the control comes to 40k, then the print statement of this function will execute and d will be printed.

Then control will come to 30k and the print statement will execute and c will be printed.

Then control will come to 20k and 10k respectively and the print statement will execute and b and a will be printed in order.

That was easy. Wasn't it?

import java.io.*; import java.util.*; public class Main { public static class Node { int data; Node next; } public static class LinkedList { Node head; Node tail; int size; void addLast(int val) { Node temp = new Node(); temp.data = val; temp.next = null; if (size == 0) { head = tail = temp; } else { tail.next = temp; tail = temp; } size++; } public int size() { return size; } public void display() { for (Node temp = head; temp != null; temp = temp.next) { System.out.print(temp.data + " "); } System.out.println(); } public void removeFirst() { if (size == 0) { System.out.println("List is empty"); } else if (size == 1) { head = tail = null; size = 0; } else { head = head.next; size--; } } public int getFirst() { if (size == 0) { System.out.println("List is empty"); return -1; } else { return head.data; } } public int getLast() { if (size == 0) { System.out.println("List is empty"); return -1; } else { return tail.data; } } public int getAt(int idx) { if (size == 0) { System.out.println("List is empty"); return -1; } else if (idx < 0 || idx >= size) { System.out.println("Invalid arguments"); return -1; } else { Node temp = head; for (int i = 0; i < idx; i++) { temp = temp.next; } return temp.data; } } public void addFirst(int val) { Node temp = new Node(); temp.data = val; temp.next = head; head = temp; if (size == 0) { tail = temp; } size++; } public void addAt(int idx, int val) { if (idx < 0 || idx > size) { System.out.println("Invalid arguments"); } else if (idx == 0) { addFirst(val); } else if (idx == size) { addLast(val); } else { Node node = new Node(); node.data = val; Node temp = head; for (int i = 0; i < idx - 1; i++) { temp = temp.next; } node.next = temp.next; temp.next = node; size++; } } public void removeLast() { if (size == 0) { System.out.println("List is empty"); } else if (size == 1) { head = tail = null; size = 0; } else { Node temp = head; for (int i = 0; i < size - 2; i++) { temp = temp.next; } tail = temp; tail.next = null; size--; } } public void removeAt(int idx) { if (idx < 0 || idx >= size) { System.out.println("Invalid arguments"); } else if (idx == 0) { removeFirst(); } else if (idx == size - 1) { removeLast(); } else { Node temp = head; for (int i = 0; i < idx - 1; i++) { temp = temp.next; } temp.next = temp.next.next; size--; } } private Node getNodeAt(int idx) { Node temp = head; for (int i = 0; i < idx; i++) { temp = temp.next; } return temp; } public void reverseDI() { int li = 0; int ri = size - 1; while (li < ri) { Node left = getNodeAt(li); Node right = getNodeAt(ri); int temp = left.data; left.data = right.data; right.data = temp; li++; ri--; } } public void reversePI() { if (size <= 1) { return; } Node prev = null; Node curr = head; while (curr != null) { Node next = curr.next; curr.next = prev; prev = curr; curr = next; } Node temp = head; head = tail; tail = temp; } public int kthFromLast(int k) { Node slow = head; Node fast = head; for (int i = 0; i < k; i++) { fast = fast.next; } while (fast != tail) { slow = slow.next; fast = fast.next; } return slow.data; } public int mid() { Node f = head; Node s = head; while (f.next != null && f.next.next != null) { f = f.next.next; s = s.next; } return s.data; } public static LinkedList mergeTwoSortedLists(LinkedList l1, LinkedList l2) { LinkedList ml = new LinkedList(); Node one = l1.head; Node two = l2.head; while (one != null && two != null) { if (one.data < two.data) { ml.addLast(one.data); one = one.next; } else { ml.addLast(two.data); two = two.next; } } while (one != null) { ml.addLast(one.data); one = one.next; } while (two != null) { ml.addLast(two.data); two = two.next; } return ml; } public static Node midNode(Node head, Node tail) { Node f = head; Node s = head; while (f != tail && f.next != tail) { f = f.next.next; s = s.next; } return s; } public static LinkedList mergeSort(Node head, Node tail) { if (head == tail) { LinkedList br = new LinkedList(); br.addLast(head.data); return br; } Node mid = midNode(head, tail); LinkedList fsh = mergeSort(head, mid); LinkedList ssh = mergeSort(mid.next, tail); LinkedList sl = mergeTwoSortedLists(fsh, ssh); return sl; } public void removeDuplicates() { LinkedList res = new LinkedList(); while (this.size() > 0) { int val = this.getFirst(); this.removeFirst(); if (res.size() == 0 || val != res.tail.data) { res.addLast(val); } } this.head = res.head; this.tail = res.tail; this.size = res.size; } public void oddEven() { LinkedList odd = new LinkedList(); LinkedList even = new LinkedList(); while (this.size > 0) { int val = this.getFirst(); this.removeFirst(); if (val % 2 == 0) { even.addLast(val); } else { odd.addLast(val); } } if (odd.size > 0 && even.size > 0) { odd.tail.next = even.head; this.head = odd.head; this.tail = even.tail; this.size = odd.size + even.size; } else if (odd.size > 0) { this.head = odd.head; this.tail = odd.tail; this.size = odd.size; } else if (even.size > 0) { this.head = even.head; this.tail = even.tail; this.size = even.size; } } public void kReverse(int k) { LinkedList prev = null; while (this.size > 0) { LinkedList curr = new LinkedList(); if (this.size >= k) { for (int i = 0; i < k; i++) { int val = this.getFirst(); this.removeFirst(); curr.addFirst(val); } } else { int sz = this.size; for (int i = 0; i < sz; i++) { int val = this.getFirst(); this.removeFirst(); curr.addLast(val); } } if (prev == null) { prev = curr; } else { prev.tail.next = curr.head; prev.tail = curr.tail; prev.size += curr.size; } } this.head = prev.head; this.tail = prev.tail; this.size = prev.size; } private void displayReverseHelper(Node node){ if(node == null){ return; } displayReverseHelper(node.next); System.out.print(node.data + " "); } public void displayReverse(){ displayReverseHelper(head); System.out.println(); } } public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n1 = Integer.parseInt(br.readLine()); LinkedList l1 = new LinkedList(); String[] values1 = br.readLine().split(" "); for (int i = 0; i < n1; i++) { int d = Integer.parseInt(values1[i]); l1.addLast(d); } int a = Integer.parseInt(br.readLine()); int b = Integer.parseInt(br.readLine()); l1.display(); l1.displayReverse(); l1.addLast(a); l1.addFirst(b); l1.display(); } }
java; true";
Analysis:
Time Complexity:

O(n)

As 'n' recursive calls are made, n being the size of the linked list, therefore making the time complexity O(n).

Space Complexity:

O(1)

And since no extra space has been used, therefore the space complexity remains constant.

Our desire to make you learn will remain unsatisfactory if you still have doubts. We strongly recommend you to watch our video lecture on Display Reverse Recursive for clearing any type of doubts.

Suggestions and feedback are always welcomed. You can contact us via our website.

All the best for a bright future!

Happy Coding!

Linked lists
Display Reverse Linked List
Recursion
Author: Nikita Aggarwal
 
Run
Id Name