I know how to reverse the link list,but if I want to compare the reversed link list with the original link list ,I don’t know how to store the original link list ,how to do that???
Doubt in the concept of reversing
you don’t need to reverse the whole linked list. just reverse it from half.
now you will have two head pointers, one from start, and second from last.
you can now compare one by one until both head pointed are NULL.
thanks.
time limit error in this code.
you have problem in this section.
int left =0;
int rigth=(this.size()/2)-1;
boolean ans=false;
while(left<rigth){
Node ln=getNodeAt(left);
Node rn=getNodeAt(rigth);
int temp=ln.data;
ln.data=rn.data;
rn.data=temp;
}
your while loop will never terminate… sine left < right will always be true.
you need to learn how to reverse a linked list.
try to write a code that reverses a given linked list.
then follow the approach I suggested earlier.
thanks
I have tried the code ,still 2 test cases are failing
lets start from another question because i can not directly give you the complete code, its not recommended.
given a linked list, your task is to reverse it.
can you please write a code that simply reverses the linked list.
thanks
public void reverse(int l, int r) throws Exception{
int left = l;
int right = r;
while (left < right) {
Node ln = getNodeAt(left);
Node rn = getNodeAt(right);
int temp = ln.data;
ln.data = rn.data;
rn.data = temp;
left++;
right–;
}
// Write your code here
}
this is the function for reverse
where left=0;
rigth=size-1;
Sir,I also want some advise regarding my study pattern ,I have completed recursion,stack queue and link list ,now I am taking 1-1 challenge from each of the topics on daily basis ,Is this good approach or should I do something different.And along this I am going to start the tree very soon after completion of tree I 'll be doing tree challenges along with these topics.
And one more advise ,how am I going to asses myself once I am done with the challenges,because I am able to understand the questions but not able to get the right answer for every question,do I need to worry about ???
first lets talk about the solution.
to reverse the list you are swapping the data. right?
what is palindrome? instead of swapping the data, if you just compare the data, you will cover palindrome too. if anytime comparison is false, it means its not a palindrome.
I made changes in your ispalindrome() method…check it…
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 boolean isPalindrome()throws Exception {
if(this.size()==1)
return true;
int left = this.size()/2-1;
int right = this.size()/2;
if(this.size()%2!=0){
right++;
}
while(left>=0){
Node ln=getNodeAt(left);
Node rn=getNodeAt(right);
if(ln.data!=rn.data)
return false;
left--;
right++;
}
return true;
}
public static void main(String[] args) throws Exception {
Scanner scn = new Scanner(System.in);
int N = scn.nextInt();
LinkedList list = new LinkedList();
for (int i = 0; i < N; i++) {
list.addLast(scn.nextInt());
}
System.out.println(list.isPalindrome());
}
}
now, your study pattern seems fine to me. when you wont able to do a question, that’s not a problem at all, but the important thing is you must assess the approach to that problem and try to code the problem once again. if you wont able to understand that problem even in 2 days, leave it … don’t waste time in it… you can check that question again in a month or later.
this is not a right time to assess yourself. you are in a learning phase. try to learn the concepts as much as you can. if you don’t get any question, no problem, check its solution, read it, try to understand it. even if you don’t understand it, leave the question at that time, and try that question again after a week or two week…
once you are done with atleast 150 questions, may be 20-30 from each topic… you can start competitive coding… then that will be right time to assess yourself.
thanks
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.
this was my code I am having certain doubt regarding the use this keyword in this code ,when we are calling some other function we calling using this but when we are functions inside ispalindrome function we are not using this keyword
@Adhyayan,
https://ide.codingblocks.com/s/269015 corrected code.
Your code is correct, the error is that you need to rename LinkedList class to Main class. There has to be a Main class in your code. Hence the error.
So just change the name of object, class,constructors to Main instead of LinkedList and your code should submit
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.