Remove Last from the linked list

tanishka972 · April 17, 2020, 5:58pm

In this second case u said that size is 1 when there is only one node.But in previous case when their are more than 2, 3 nodes u consider the size from 0 to n-1 then why should u consider size one in fst case rather than 0?

kashishsingh8700 · April 17, 2020, 6:06pm

hi @tanishka972
in first case when we have 2 or more nodes the we simply get the node at size-2 because our indexing starts from 0 but in second case when size is equal to 1 the we cannot access size-2 it will give us index out of bound error so we handle it seperately.

kashishsingh8700 · April 22, 2020, 1:39pm

@tanishka972
please mark your doubt as resolved in my doubts section and rate me as well.

tanishka972 · April 22, 2020, 2:09pm

ok, I have one more question that In LL-k reverse problem,while we calling that reverse function
then pass two parameters their one is node type another is int type.But it shows error

public class LinkedList {
private class Node {
int data;
Node next;

	Node(int data, Node next) {
		this.data = data;
		this.next = next;
	}
}

private Node head;
private Node tail;
private int size;

public LinkedList() {
	this.head = null;
	this.tail = null;
	this.size = 0;
}

public LinkedList(Node head, Node tail, int size) {
	this.head = head;
	this.tail = tail;
	this.size = size;
}

// O(1)
public int size() {
	return this.size;
}

// O(1)
public boolean isEmpty() {
	return this.size() == 0;
}

// O(1)
public int getFirst() throws Exception {
	if (this.isEmpty()) {
		throw new Exception("List is empty.");
	}

	return this.head.data;
}

// O(1)
public int getLast() throws Exception {
	if (this.isEmpty()) {
		throw new Exception("List is empty.");
	}

	return this.tail.data;
}

// O(N)
public int getAt(int idx) throws Exception {
	Node temp = this.getNodeAt(idx);
	return temp.data;
}

// O(N)
private Node getNodeAt(int idx) throws Exception {
	if (this.isEmpty()) {
		throw new Exception("List is empty");
	}

	if (idx < 0 || idx >= this.size()) {
		throw new Exception("Invalid arguments");
	}

	Node retVal = this.head;
	for (int i = 0; i < idx; i++) {
		retVal = retVal.next;
	}

	return retVal;
}

// O(1)
public void addFirst(int data) {
	Node node = new Node(data, this.head);

	if (this.size() == 0) {
		this.head = node;
		this.tail = node;
	} else {
		this.head = node;
	}

	this.size++;
}

// O(1)
public void addLast(int data) {
	Node node = new Node(data, null);

	if (this.size() == 0) {
		this.head = node;
		this.tail = node;
	} else {
		this.tail.next = node;
		this.tail = node;
	}

	this.size++;
}

// O(n)
public void addAt(int idx, int data) throws Exception {
	if (idx < 0 || idx > this.size()) {
		throw new Exception("Invalid arguments");
	}

	if (idx == 0) {
		this.addFirst(data);
	} else if (idx == this.size()) {
		this.addLast(data);
	} else {
		Node nm1 = this.getNodeAt(idx - 1);
		Node n = nm1.next;

		Node node = new Node(data, n);
		nm1.next = node;

		this.size++;
	}
}

// O(1)
public int removeFirst() throws Exception {
	if (this.isEmpty()) {
		throw new Exception("List is empty");
	}

	int retVal = this.head.data;

	if (this.size() == 1) {
		this.head = null;
		this.tail = null;
	} else {
		this.head = this.head.next;
	}

	this.size--;
	return retVal;
}

// O(n)
public int removeLast() throws Exception {
	if (this.isEmpty()) {
		throw new Exception("List is empty");
	}

	int retVal = this.tail.data;

	if (this.size() == 1) {
		this.head = null;
		this.tail = null;
	} else {
		Node sm2 = this.getNodeAt(this.size() - 2);
		sm2.next = null;
		this.tail = sm2;
	}

	this.size--;
	return retVal;
}

// O(n)
public int removeAt(int idx) throws Exception {
	if (this.isEmpty()) {
		throw new Exception("List is empty");
	}

	if (idx < 0 || idx >= this.size()) {
		throw new Exception("Invalid arguments");
	}

	if (idx == 0) {
		return this.removeFirst();
	} else if (idx == this.size() - 1) {
		return this.removeLast();
	} else {
		Node nm1 = this.getNodeAt(idx - 1);
		Node n = nm1.next;
		Node np1 = n.next;

		nm1.next = np1;
		this.size--;

		return n.data;
	}
}

// O(n)
public void display() {
	Node node = this.head;

	while (node != null) {
		System.out.print(node.data + " ");
		node = node.next;
	}

	//System.out.println("END");
}

Node reverse(Node head, int k)
{

   Node current = head; 
   Node next = null; 
   Node prev = null; 

   int count = 0; 

   /* Reverse first k nodes of linked list */
   while (count < k && current != null)  
   { 
       next = current.next; 
       current.next = prev; 
       prev = current; 
       current = next; 
       count++; 
   } 


   if (next != null)  
      head.next = reverse(next, k); 


   return prev;

}

public static void main(String[] args) throws Exception {

	Scanner scn = new Scanner(System.in);
	int N = scn.nextInt();
    int k = scn.nextInt();
	
	LinkedList list = new LinkedList();

	for (int i = 0; i < N; i++) {
		list.addLast(scn.nextInt());
	}

    list.reverse(N,k);--------->this line shows error.
	list.display();

}
}

kashishsingh8700 · April 22, 2020, 2:40pm

@tanishka972
just pass list head in the argument
list.reverse(list.head,k);

tanishka972 · April 22, 2020, 2:47pm

still shows this exception
Exception in thread “main” java.util.NoSuchElementException
at java.util.Scanner.throwFor(Scanner.java:862)
at java.util.Scanner.next(Scanner.java:1485)
at java.util.Scanner.nextInt(Scanner.java:2117)
at java.util.Scanner.nextInt(Scanner.java:2076)
at LinkedList.main(LinkedList.java:243)

kashishsingh8700 · April 22, 2020, 2:50pm

@tanishka972
before compile and run write the testcases in the box

tanishka972 · April 22, 2020, 2:53pm

in that box where i write program?

kashishsingh8700 · April 22, 2020, 2:59pm

@tanishka972
no below the compile and run button

tanishka972 · April 22, 2020, 3:05pm

will I write all test cases in that box

kashishsingh8700 · April 22, 2020, 3:09pm

@tanishka972
if you to check a particular testcase otherwise you can directly submit

tanishka972 · April 22, 2020, 3:11pm

when I wrote a particular test case and submit it then it shows only one test case pass other shows cross mark.How will I pass all test cases?

kashishsingh8700 · April 22, 2020, 3:11pm

@tanishka972
let me correct your code then

kashishsingh8700 · April 22, 2020, 3:18pm

@tanishka972
import java.util.*;
public class LinkedList {
private class Node {
int data;
Node next;

	Node(int data, Node next) {
		this.data = data;
		this.next = next;
	}
}

private Node head;
private Node tail;
private int size;

public LinkedList() {
	this.head = null;
	this.tail = null;
	this.size = 0;
}

public LinkedList(Node head, Node tail, int size) {
	this.head = head;
	this.tail = tail;
	this.size = size;
}

// O(1)
public int size() {
	return this.size;
}

// O(1)
public boolean isEmpty() {
	return this.size() == 0;
}

// O(1)
public int getFirst() throws Exception {
	if (this.isEmpty()) {
		throw new Exception("List is empty.");
	}

	return this.head.data;
}

// O(1)
public int getLast() throws Exception {
	if (this.isEmpty()) {
		throw new Exception("List is empty.");
	}

	return this.tail.data;
}

// O(N)
public int getAt(int idx) throws Exception {
	Node temp = this.getNodeAt(idx);
	return temp.data;
}

// O(N)
private Node getNodeAt(int idx) throws Exception {
	if (this.isEmpty()) {
		throw new Exception("List is empty");
	}

	if (idx < 0 || idx >= this.size()) {
		throw new Exception("Invalid arguments");
	}

	Node retVal = this.head;
	for (int i = 0; i < idx; i++) {
		retVal = retVal.next;
	}

	return retVal;
}

// O(1)
public void addFirst(int data) {
	Node node = new Node(data, this.head);

	if (this.size() == 0) {
		this.head = node;
		this.tail = node;
	} else {
		this.head = node;
	}

	this.size++;
}

// O(1)
public void addLast(int data) {
	Node node = new Node(data, null);

	if (this.size() == 0) {
		this.head = node;
		this.tail = node;
	} else {
		this.tail.next = node;
		this.tail = node;
	}

	this.size++;
}

// O(n)
public void addAt(int idx, int data) throws Exception {
	if (idx < 0 || idx > this.size()) {
		throw new Exception("Invalid arguments");
	}

	if (idx == 0) {
		this.addFirst(data);
	} else if (idx == this.size()) {
		this.addLast(data);
	} else {
		Node nm1 = this.getNodeAt(idx - 1);
		Node n = nm1.next;

		Node node = new Node(data, n);
		nm1.next = node;

		this.size++;
	}
}

// O(1)
public int removeFirst() throws Exception {
	if (this.isEmpty()) {
		throw new Exception("List is empty");
	}

	int retVal = this.head.data;

	if (this.size() == 1) {
		this.head = null;
		this.tail = null;
	} else {
		this.head = this.head.next;
	}

	this.size--;
	return retVal;
}

// O(n)
public int removeLast() throws Exception {
	if (this.isEmpty()) {
		throw new Exception("List is empty");
	}

	int retVal = this.tail.data;

	if (this.size() == 1) {
		this.head = null;
		this.tail = null;
	} else {
		Node sm2 = this.getNodeAt(this.size() - 2);
		sm2.next = null;
		this.tail = sm2;
	}

	this.size--;
	return retVal;
}

// O(n)
public int removeAt(int idx) throws Exception {
	if (this.isEmpty()) {
		throw new Exception("List is empty");
	}

	if (idx < 0 || idx >= this.size()) {
		throw new Exception("Invalid arguments");
	}

	if (idx == 0) {
		return this.removeFirst();
	} else if (idx == this.size() - 1) {
		return this.removeLast();
	} else {
		Node nm1 = this.getNodeAt(idx - 1);
		Node n = nm1.next;
		Node np1 = n.next;

		nm1.next = np1;
		this.size--;

		return n.data;
	}
}

// O(n)
public void display() {
	Node node = this.head;

	while (node != null) {
		System.out.print(node.data + " ");
		node = node.next;
	}

	//System.out.println("END");
}

public Node reverse(Node head,int k){

     Node current = head; 
   Node next = null; 
   Node prev = null; 

   int count = 0; 

  
   while (count < k && current != null)  
   { 
       next = current.next; 
       current.next = prev; 
       prev = current; 
       current = next; 
       count++; 
   } 

   
   if (next != null)  
      head.next = reverse(next, k); 

  
   return prev; 

}

public static void main(String[] args) throws Exception {

	Scanner scn = new Scanner(System.in);
	int N = scn.nextInt();
    int k = scn.nextInt();
	
	LinkedList list = new LinkedList();

	for (int i = 0; i < N; i++) {
		list.addLast(scn.nextInt());
	}

    list.head=list.reverse(list.head,k);
	list.display();

}
}

tanishka972 · April 22, 2020, 3:23pm

Thank U!!
Why It can’t pass all cases before?

kashishsingh8700 · April 22, 2020, 4:07pm

@tanishka972
earlier the list head was not assigned properly.

kashishsingh8700 · April 22, 2020, 7:30pm

@tanishka972
please mark your doubt as resolved in my doubts section and rate me as well.

kashishsingh8700 · April 24, 2020, 1:59pm

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

tanishka972 · April 24, 2020, 2:06pm

I already rate experience