Prev   Next

Reverse A Linked List (data Iterative)







First, solve the problem. Then, write the code.
~John Johnson

Reverse A Linked List (data Iterative)

Dear reader, I hope you enjoy solving these problems. We are going to solve a very popular Linked List problem. This problem can be solved in two ways. We will discuss one approach here. The other one will be discussed later.

Important Links :Problem Link, Question Video, Solution Video

Problem Discussion :
  1. You are given a partially written LinkedList class.
  2. Here is a list of existing functions:
    1. addLast - adds a new element with given value to the end of Linked List
    2. display - Prints the elements of a linked list from front to end in a single line. All elements are separated by space
    3. size - Returns the number of elements in the linked list.
    4. removeFirst - Removes the first element from Linked List.
    5. getFirst - Returns the data of the first element.
    6. getLast - Returns the data of the last element.
    7. getAt - Returns the data of the element available at the index passed.
    8. addFirst - adds a new element with a given value in front of the linked list.
    9. addAt - adds a new element at a given index.
    10. removeLast - removes the last element of the linked list.
    11. removeAt - remove an element at a given index.
  3. You are required to complete the body of the reverseDI function. The function should be an iterative function and should reverse the contents of the linked list by changing the "data" property of nodes.
  4. Input and Output is managed for you.

If you face any difficulty understanding the problem, watch the Question video.

Approach :

If we illustrate a LinkedList this way:

img

Then after reversing the LinkedList should look like:

img

Let's forget a linked list and think about reversing an array [10, 20, 30, 40, 50]. How do we do that? We can simply swap the first and the last values, then swap the second and the second last value, and so on.

img

Works also for an even number of elements. Like here:

img

In the array, we can easily get the value at the i-th position, but in the Linked List we have to write a function that will do that. Since this is just going to be used inside a class method, we will make it a private function. So what it will do is get the node at the i-th index. Then we will swap the data. So the pseudo-code for the reverse will be :

img

And what about the getNodeAt(idx) function. We can simply run a loop till idx and keep moving a dummy pointer to its next node. The dummy pointer will be initialized with the head. And after the loop is over we will return it. This function is going to be very similar to that of getAt() but there we were returning the data here we would need the node itself.

Try to code this yourself.

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 static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); LinkedList list = new LinkedList(); String str = br.readLine(); while (str.equals("quit") == false) { if (str.startsWith("addLast")) { int val = Integer.parseInt(str.split(" ")[1]); list.addLast(val); } else if (str.startsWith("size")) { System.out.println(list.size()); } else if (str.startsWith("display")) { list.display(); } else if (str.startsWith("removeFirst")) { list.removeFirst(); } else if (str.startsWith("getFirst")) { int val = list.getFirst(); if (val != -1) { System.out.println(val); } } else if (str.startsWith("getLast")) { int val = list.getLast(); if (val != -1) { System.out.println(val); } } else if (str.startsWith("getAt")) { int idx = Integer.parseInt(str.split(" ")[1]); int val = list.getAt(idx); if (val != -1) { System.out.println(val); } } else if (str.startsWith("addFirst")) { int val = Integer.parseInt(str.split(" ")[1]); list.addFirst(val); } else if (str.startsWith("addAt")) { int idx = Integer.parseInt(str.split(" ")[1]); int val = Integer.parseInt(str.split(" ")[2]); list.addAt(idx, val); } else if (str.startsWith("removeLast")) { list.removeLast(); } else if (str.startsWith("removeAt")) { int idx = Integer.parseInt(str.split(" ")[1]); list.removeAt(idx); } else if (str.startsWith("reverseDI")) { list.reverseDI(); } str = br.readLine(); } } }
java; true";
Analysis
Time Complexity:

O(n2)

The getNodeAt() function is a linear function and the number of calls to that function will be at max n. Because we will do n/2 calls for the left node and n/2 for the right node. So the total complexity is n*O(n) = O(n2)

Space Complexity:

O(1)

We are not using any extra space so the space complexity will remain constant.

I hope you have understood the problem and the explanation. If you have some doubts I would insist you watch the solution video. And try to dry run the code, this will make everything clear. See you in the next problem.

Node
Head
Linked List
Author: Arnab Sen
 
Run
Id Name