Redirecting to
NADOS


  Prev   Next

Reverse Linked List Pointer Recursive







Believe you can and you're halfway there.
~ Theodore Roosevelt

Reverse Linked List Pointer Recursive

Welcome back readers!

We hope that you are enjoying your coding 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 "Reverse a Linked List using pointers" as it is quite clear from the name that we need to reverse a linked list but using pointers.

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 recommended that you brainstorm a lot and try your best 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.
All you need to do is complete the body of reversePR and reversePRHelper functions. The functions are expected to reverse the linked list by using recursion and changing the "next" data member of nodes.
Input and Output is managed for you.

Note -> The online judge can't force you to write a recursive function, nor can it check if you changed the "next" data member or not. 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 :

f you remember the previous question which was to display the reverse, then let me tell you that even here the reason to use two functions remains the same; reversePR() and reversePRHelper() .

Out of these both reversePR() is the public one, that is the one user can access and another reversePRHelper() is the private one in which we write our main code which is to change the pointers.

Inside reversePR(), we call reversePRHelper() and then add some other changes to it.

Inside reversePRHelper(), we make a recursive call, define a base case and do some self work.

Let's assume an example side by side; where a linked list is represented as follows. We call it Llist.

img
reversePRHelper(Node node)
  • Since this is our main function therefore we will do our main part that is changing the pointers, inside this function. We will make use of recursion to do so, just like we did in our previous question.
  • It is necessary that we start to change our pointers from the end so that our Linked List doesn't break in between and we therefore fail to complete the given task.
  • So we reach to the last element making recursive calls to node.next each time.
  • Base case will be hit when node.next becomes equal to null.
  • When functions start returning, then we change node.next.next to node. This way if a is pointing towards b and b to null then b will now point to a.
  • We start to make these changes from the last second element because we don't have access to tail.next.next as tail.next is null and null has nothing like next.
  • These changes will be made till we reach the head. If a is the head and b head.next then after reversing, b points towards a but head i.e a still points towards b.
  • So when reversePRHelper() is returned to reversePR() we further make some changes.
img

If we apply the above rules on Llist then it will look like shown below.

img
reversePR()
  • When reversePRHelper() is returned to reversePR() we change the next head to null because after reversing the linked list, the original head becomes the tail.
  • Finally we swap the head and the tail pointers using a temp Node.
img

Applying the above rules on Llist we get to see following changes which are final:

img
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(); } private void reversePRHelper(Node node){ if(node == tail){ return; } reversePRHelper(node.next); node.next.next = node; } public void reversePR(){ reversePRHelper(head); Node temp = head; head = tail; tail = temp; tail.next = null; } } 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.reversePR(); 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.

That was easy. Wasn't it?

Our desire to make you learn will remain unsatisfactory if you still have doubts. We strongly recommend you to watch our video lecture on Reverse Linked List using pointer and recursion 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! Never dodge the bullet.

Happy Coding!

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