LeetCode 707. Design Linked List | Together Java | Page 1

royal raft Jun 13, 2023, 7:12 AM

#

I am getting this error in the picture. Seems to be from my get method, but I can't see how

class MyLinkedList {
    Node head;
    Node tail;
    int count;

    public class Node {
        int val;
        Node next;
        Node prev;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.prev = null;
        }
    }



    public MyLinkedList() {
        this.head = null;
        this.tail = null;
        this.count = 0;
    }
    
    public int get(int index) {
        if (index < 0 || index >= this.count) {
            return -1;
        }
        else if (head == null) {
            return -1;
        }
        Node temp = this.head;
        for (int i = 0; i < index; i ++) {
            temp = temp.next;
        }
        return temp.val;
    }

slim glacierBOT Jun 13, 2023, 7:12 AM

#

<@&987246399047479336> please have a look, thanks.

slim glacierBOT Jun 13, 2023, 7:12 AM

#

slim glacier <@&987246399047479336> please have a look, thanks.

#

While you are waiting for getting help, here are some tips to improve your experience:

Code is much easier to read if posted with syntax highlighting and proper formatting.

If nobody is calling back, that usually means that your question was not well asked and hence nobody feels confident enough answering. Try to use your time to elaborate, provide details, context, more code, examples and maybe some screenshots. With enough info, someone knows the answer for sure.

Don't forget to close your thread using the command </help-thread close:1027500463647621170> when your question has been answered, thanks.

ripe idol Jun 13, 2023, 7:18 AM

#

royal raft I am getting this error in the picture. Seems to be from my get method, but I ca...

What is the assignment?

royal raft Jun 13, 2023, 7:19 AM

#

Design your implementation of the linked list. You can choose to use a singly or doubly linked list.
A node in a singly linked list should have two attributes: val and next. val is the value of the current node, and next is a pointer/reference to the next node.
If you want to use the doubly linked list, you will need one more attribute prev to indicate the previous node in the linked list. Assume all nodes in the linked list are 0-indexed.

Implement the MyLinkedList class:

MyLinkedList() Initializes the MyLinkedList object.
int get(int index) Get the value of the indexth node in the linked list. If the index is invalid, return -1.
void addAtHead(int val) Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
void addAtTail(int val) Append a node of value val as the last element of the linked list.
void addAtIndex(int index, int val) Add a node of value val before the indexth node in the linked list. If index equals the length of the linked list, the node will be appended to the end of the linked list. If index is greater than the length, the node will not be inserted.
void deleteAtIndex(int index) Delete the indexth node in the linked list, if the index is valid.

ripe idol Jun 13, 2023, 7:37 AM

#

You have an npe at temp.next

#

@royal raft

royal raft Jun 13, 2023, 7:38 AM

#

but I don't get how I can get a nullpointer if the index it goes to will not be

ripe idol Jun 13, 2023, 7:43 AM

#

royal raft but I don't get how I can get a nullpointer if the index it goes to will not be

Then count is wrong 🤔

royal raft Jun 13, 2023, 7:47 AM

#

   public void addAtHead(int val) {
        Node newNode = new Node(val);
        newNode.next = head;
        head = newNode;
        count ++;
        if (count == 1) {
            tail = head;
        }
    }
    
    public void addAtTail(int val) {
        Node newNode = new Node(val);
        newNode.prev = tail;
        tail.next = newNode;
        tail = newNode;
        count ++;
        if (count == 1) {
            head = tail;
        }
    }
    
    public void addAtIndex(int index, int val) {
        if (index < 0 || index > count) {
            return;
        }
        else if (index == count) {
            addAtTail(val);
        }
        else if (index == 0) {
            addAtHead(val);
        }

        Node newNode = new Node(val);

        Node temp = head;
        for (int i = 0; i < index; i ++) {
            temp = temp.next;
        }
        newNode.prev = temp.prev;
        newNode.next = temp.next;
        temp.prev.next = newNode;
        temp.prev = newNode;
        count ++;

    }

slim glacierBOT Jun 13, 2023, 7:47 AM

#

royal raft ```java public void addAtHead(int val) { Node newNode = new Node(val)...

Detected code, here are some useful tools:

Formatted code

public void addAtHead(int val) {
  Node newNode = new Node(val);
  newNode.next = head;
  head = newNode;
  count++;
  if (count == 1) {
    tail = head;
  }
}
public void addAtTail(int val) {
  Node newNode = new Node(val);
  newNode.prev = tail;
  tail.next = newNode;
  tail = newNode;
  count++;
  if (count == 1) {
    head = tail;
  }
}
public void addAtIndex(int index, int val) {
  if (index < 0 || index > count) {
    return ;
  }
  else if (index == count) {
    addAtTail(val);
  }
  else if (index == 0) {
    addAtHead(val);
  }
  Node newNode = new Node(val);
  Node temp = head;
  for (int i = 0; i < index; i++) {
    temp = temp.next;
  }
  newNode.prev = temp.prev;
  newNode.next = temp.next;
  temp.prev.next = newNode;
  temp.prev = newNode;
  count++;
}

royal raft Jun 13, 2023, 7:47 AM

#

    
    public void deleteAtIndex(int index) {
        if (index < 0 || index >= count) {
            return;
        }
        else if (index == 0) {
            head = head.next;
            count --;
            if (count == 1) {
            tail = head;
            }
            return;
        }
        else if (index == count - 1) {
            tail = tail.prev;
            count --;
            if (count == 1) {
                head = tail;            
            }
            return;
        }
        else {
            Node temp = head;
            for (int i = 0; i < index; i ++) {
                temp = temp.next;
            }

            if (temp.next != null && temp.prev != null) {
                temp.prev.next = temp.next;
                temp.next.prev = temp.prev;
                temp.next = null;
                temp.prev = null;
                count --;
            }
            else if (temp.next == null && temp.prev != null){
                tail = temp.prev;
                temp.prev.next = null;
                count --;
            }
            else if (temp.prev == null && temp.next != null) {
                head = temp.next;
                temp.next.prev = null;
                count --;
            }
        }
    }  
}

the rest of the code

slim glacierBOT Jun 13, 2023, 7:47 AM

#

royal raft ```java public void deleteAtIndex(int index) { if (index < 0 ||...

Detected code, here are some useful tools:

royal raft Jun 13, 2023, 7:48 AM

#

the count seems to be incrementing and decrementing correctly

ripe idol Jun 13, 2023, 7:52 AM

#

royal raft the count seems to be incrementing and decrementing correctly

In addAtIndex, you are calling addAtHead/Tail and then adding it manually? So you add twice ?

royal raft Jun 13, 2023, 7:53 AM

#

    
    public void addAtIndex(int index, int val) {
        if (index < 0 || index > count) {
            return;
        }
        else if (index == count) {
            addAtTail(val);
            return;
        }
        else if (index == 0) {
            addAtHead(val);
            return;
        }

        Node newNode = new Node(val);

        Node temp = head;
        for (int i = 0; i < index; i ++) {
            temp = temp.next;
        }
        newNode.prev = temp.prev;
        newNode.next = temp.next;
        temp.prev.next = newNode;
        temp.prev = newNode;
        count ++;

    }

i changed to this

#

still doesn't work ):

ripe idol Jun 13, 2023, 7:54 AM

#

royal raft ```java public void addAtIndex(int index, int val) { if (index ...

What did you change? You still add twice

#

Ah my bad

#

No

royal raft Jun 13, 2023, 7:59 AM

#

still wrong?

ripe idol Jun 13, 2023, 7:59 AM

#

🤔

#

The best you can do is to move the code to your ide and debug it

#

@royal raft

royal raft Jun 13, 2023, 8:11 AM

#

ummm

#

this is odd

#

is anyone else spot something wrong

worthy adder Jun 13, 2023, 8:40 AM

#

yea from what i can tell, you are jumping one node when you set newNode.next=temp.next, shouldnt it be just newNode.next=temp

#

@royal raft

#

basically your temp pointer ends at i+1th val, which you skip.

#

this is a representation of the whole process

#

wait i think i made a mistake in 3rd step, you were right about temp.prev.next=newNode step

#

but newNode.next=temp this should be the next step

royal raft Jun 13, 2023, 9:04 AM

#

    public void addAtIndex(int index, int val) {
        if (index < 0 || index > count) {
            return;
        }
        else if (index == count) {
            addAtTail(val);
            return;
        }
        else if (index == 0) {
            addAtHead(val);
            return;
        }

        Node newNode = new Node(val);

        Node temp = head;
        for (int i = 0; i < index; i ++) {
            temp = temp.next;
        }
        newNode.prev = temp.prev;
        newNode.next = temp;
        temp.prev.next = newNode;
        temp.prev = newNode;
        count ++;

    }

so like this?

#

u r right

#

it passed 2/65 tests after changing to just temp

#

#

@worthy adderscratching my head

worthy adder Jun 13, 2023, 9:09 AM

#

wait, was it throwing next as null before you made the suggested changes?

royal raft Jun 13, 2023, 9:09 AM

#

I don't pass any tests before the change

worthy adder Jun 13, 2023, 9:11 AM

#

ill take a look at this in few mins, need to do some stuff.

royal raft Jun 13, 2023, 9:11 AM

#

No rush! I think i have to head to bed, but i will come back to this tomorrow

merry imp Jun 13, 2023, 9:27 AM

#

royal raft ```java public void deleteAtIndex(int index) { if (index < 0 ||...

        else if (index == count - 1) {
            tail = tail.prev;
            // YOU DIDN'T SET tail.next to null
            count --;
            if (count == 1) {
                head = tail;            
            }
            return;
        }

#

i think this is (one of) the reasons of your mismatch between count and the actual size of the linked list

#

same with the case of deleting the head, you should probably set head.prev = null

worthy adder Jun 13, 2023, 9:29 AM

#

if there's a problem with count it might explain the reason for temp.next being null

slim glacierBOT Jun 13, 2023, 10:16 PM

#

Closed the thread due to inactivity.

If your question was not resolved yet, feel free to just post a message to reopen it, or create a new thread. But try to improve the quality of your question to make it easier to help you 👍

royal raft Jun 14, 2023, 12:32 AM

#

@merry imp Hi thank you for reading my code, I just updated this method, but the error persists at the same place

    public void deleteAtIndex(int index) {
        if (index < 0 || index >= count) {
            return;
        }
        else if (index == 0) {
            head = head.next;
            count --;
            if (count == 1) {
            tail = head;
            tail.next = null;
            }
            return;
        }
        else if (index == count - 1) {
            tail = tail.prev;
            tail.next = null;
            count --;
            if (count == 1) {
                head = tail; 
                head.prev = null;           
            }
            return;
        }
        else {
            Node temp = head;
            for (int i = 0; i < index; i ++) {
                temp = temp.next;
            }

            if (temp.next != null && temp.prev != null) {
                temp.prev.next = temp.next;
                temp.next.prev = temp.prev;
                temp.next = null;
                temp.prev = null;
                count --;
            }
            else if (temp.next == null && temp.prev != null){
                tail = temp.prev;
                tail.next = null;
                count --;
            }
            else if (temp.prev == null && temp.next != null) {
                head = temp.next;
                head.prev = null;
                count --;
            }
        }
    }

#

open fractal Jun 14, 2023, 6:40 AM

#

royal raft

Are these different variables by any chance?

#

maybe this.head is null, but head isn't

Idk where the head would be coming from but it looks like it's highlighed as a local variable

#

The only explanation I can find..

royal raft Jun 14, 2023, 6:41 AM

#

open fractal maybe `this.head` is null, but `head` isn't Idk where the `head` would be comin...

should be the same variable

#

they are both the heads of this linkedlist

open fractal Jun 14, 2023, 6:43 AM

#

<local2> refers to temp I believe, so somehow temp is null at some point

#

try logging temp in the loop

royal raft Jun 14, 2023, 6:44 AM

#

what do you mean by logging? Sorry I am still kinda new to coding

open fractal Jun 14, 2023, 6:45 AM

#

you can log a message to the console in the loop
System.out.println("Hello world")

royal raft Jun 14, 2023, 6:45 AM

#

Oh I see

#

but i don't think i can do this on leetcode tho

open fractal Jun 14, 2023, 6:45 AM

#

same thing as printing or whatever you wanna call it

#

uhh hmm you can at least try

#

try to log the temp.next variable in the loop System.out.println(temp.next)

royal raft Jun 14, 2023, 6:46 AM

#

#

so something like this

open fractal Jun 14, 2023, 6:47 AM

#

that works, however move it before you assign temp

#

because the error happens at the line above

royal raft Jun 14, 2023, 6:47 AM

#

yikes

open fractal Jun 14, 2023, 6:47 AM

#

and we want to know what the value is before the error happens

#

.. dang

royal raft Jun 14, 2023, 6:47 AM

#

open fractal Jun 14, 2023, 6:47 AM

#

lemme check

royal raft Jun 14, 2023, 6:47 AM

#

i had a typo lol

open fractal Jun 14, 2023, 6:48 AM

#

oh

#

WHAAAT

#

???

#

you check if this.head is null, then return
this.head can't be null anymore
temp is assigned this.head (it can't be null because this.head can't be null)
then an error happens because temp is null

#

??

royal raft Jun 14, 2023, 6:50 AM

#

IKR

#

I DONT UNDERSTAND

open fractal Jun 14, 2023, 6:50 AM

#

wait I do

#

actually

#

look

#

it ran 3 times

#

it printed/logged the node

#

so the 3d node has next set to null

royal raft Jun 14, 2023, 6:52 AM

#

but how

#

my index shouldn't allow it to go to a null node tho

open fractal Jun 14, 2023, 6:52 AM

#

how many elements were there in the list

#

in total

#

3?

royal raft Jun 14, 2023, 6:52 AM

#

i am not sure

#

idk what the test cases put

#

idk how to read this

#

oh wait i might

#

each string with its argument

open fractal Jun 14, 2023, 6:54 AM

#

try logging this.count

royal raft Jun 14, 2023, 6:54 AM

#

#

the val

open fractal Jun 14, 2023, 6:55 AM

#

the does make sense

#

there is still something wrong with the deleteAtIndex

royal raft Jun 14, 2023, 6:56 AM

#

with count

open fractal Jun 14, 2023, 6:56 AM

#

yeah I think the count is correct

#

but the deleteAtIndex sets something to null that it shouldn't

#

or doesn't set next properly

#

I'm really sorry I gotta head to school ;-;

royal raft Jun 14, 2023, 6:57 AM

#

that's ok!

open fractal Jun 14, 2023, 6:57 AM

#

Good luck, have fun solving!

royal raft Jun 14, 2023, 6:57 AM

#

thank you so much for helping, i didn't know i could print on leetcode console, now i know

open fractal Jun 14, 2023, 7:01 AM

#

Oh yeah one thing
The example input is exactly what methods leetcode calls with what arguments
So MyLinkedList means it creates a new MyLinkedList, and the [] means no arguments are given

#

So after that it calls addAtHead with the argument 7

#

Or addAtHead(7)

#

Try to walk through step by step what the state of the list is after each method call

royal raft Jun 14, 2023, 7:10 AM

#

ok thank you!

royal raft Jun 14, 2023, 7:34 AM

#

    
    public void deleteAtIndex(int index) {
        if (index < 0 || index >= count) {
            return;
        }
        else if (count == 1) {
            head = null;
            tail = null;
            count --;
            return ;
        }
        else if (index == 0) {
            head = head.next;
            count --;
            if (count == 1) {
            tail = head;
            tail.next = null;
            }
            return;
        }
        else if (index == count - 1) {
            tail = tail.prev;
            tail.next = null;
            count --;
            if (count == 1) {
                head = tail; 
                head.prev = null;           
            }
            return;
        }
        else {
            Node temp = head;
            for (int i = 0; i < index; i ++) {
                temp = temp.next;
            }

            if (temp.next != null && temp.prev != null) {
                temp.prev.next = temp.next;
                temp.next.prev = temp.prev;
                temp.next = null;
                temp.prev = null;
                count --;
            }
            else if (temp.next == null && temp.prev != null){
                tail = temp.prev;
                tail.next = null;
                count --;
            }
            else if (temp.prev == null && temp.next != null) {
                head = temp.next;
                head.prev = null;
                count --;
            }
        }
    }

made more updates to my deleteatindex to take care of situations when there is only 1 node left before delete

#LeetCode 707. Design Linked List