Dear reader, I hope you enjoy solving these problems. This problem is very similar to the previous one, except we are going to approach it differently.
Important Links :Problem Link, Question Video, Solution Video
Prev Next
Reverse Linked List (pointer Iterative)
Problem Discussion :
- You are given a partially written LinkedList class.
- Here is a list of existing functions:
- addLast - adds a new element with a given value to the end of the Linked List
- display - Prints the elements of the linked list from front to end in a single line. All elements are separated by space
- size - Returns the number of elements in the linked list.
- removeFirst - Removes the first element from Linked List.
- getFirst - Returns the data of the first element.
- getLast - Returns the data of the last element.
- getAt - Returns the data of the element available at the index passed.
- addFirst - adds a new element with a given value in front of the linked list.
- addAt - adds a new element at a given index.
- removeLast - removes the last element of the linked list.
- removeAt - remove an element at a given index
- You are required to complete the body of the reversePI function. The function should be an iterative function and should reverse the contents of the linked list by changing the "next" property of nodes.
- Input and Output are managed for you.
If you face any difficulty understanding the problem, watch the Question video.
Approach :
So, if your linked list was initially something like this:
After reversing the Linked List by changing only the pointers we should have:
If you notice carefully all we have done is reversed the pointers, now the next node is storing the address of the prev node, and so on.
All we need to do is change the current node next to the previous one. But if we do that, how shall we move to the next node? Because right now next is pointing to the previous, so we will have to keep a temporary backup of the next node, before updating the data.
So initially we will have two pointers, prev, and cur. prev will be null and cur will be head. We will also have a temp variable to store the next node. Basically, before doing anything to prev and cur, we will do:
temp = cur.next
Now we can do,
cur.next = prev
prev = cur
cur = temp
So, after this operation it will look like this:
We will again store the next pointer in temp.
temp = curr.next
Now we can do the reversing part,
cur.next = prev
prev = cur
cur = temp
Clearly, we can see that the first two nodes have been reversed, we can continue this as long as cur doesn't reach null.
After the linked list has been reversed we need to swap the head and tail.
If you faced any difficulty in this part, watch the video. If you have understood, try to write the code by 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 void reversePI() {
Node prev = null;
Node curr = head;
while (curr != null) {
Node temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
Node t = head;
head = tail;
tail = t;
}
}
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();
} else if (str.startsWith("reversePI")) {
list.reversePI();
}
str = br.readLine();
}
}
}
java;
true";
Analysis
Time Complexity:
O(n)
This is a much more efficient approach compared to the previous one where we dealt with data. Here we are just running a linear loop, so the time complexity is O(n).
Space Complexity:
O(1)
We are not using any auxiliary space, hence the space complexity is O(1).
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.
