Get kth node from the end in linked lists

Data Structures
1

hi,
in the implementation of getting the kth node from the end(linked lists), Mosh used the addLast() method to insert items in the linked list and it did work perfectly with getKthFromTheEnd(). But when we use the addFirst() method to insert items, it didn’t work!
if the implementation is correct, it should always work in any state .

1 Like
2

somebody can answer me, please? :pray:

3

In Mosh’s The Ultimate Data Structures & Algorithms: Part 1 , “Linked Lists” section, “Kth Node from the End” video, the addLast() and addFirst() methods are used to add new items to the linked list. We should then be able to then use getKthFromTheEnd() to find any node in the linked list.

The question is, does the addFirst() method properly add items to the linked list? And does using the getKthFromTheEnd() method work after adding items using the addFirst() method?

I just did the following test and my output came out as expected.

public class Main {
    public static void main(String[] args) {
        LinkedList myList = new LinkedList();
        myList.addFirst(10);
        myList.addFirst(20);
        myList.addFirst(30);
        myList.addFirst(40);
        myList.addFirst(50);
        myList.addFirst(60);
        myList.addFirst(70);
        myList.addFirst(80);
        myList.reverse();
        var array = myList.toArray();
        System.out.println(Arrays.toString(array));
        System.out.println(myList.findKthFromTheEnd(8));
    }
}

The above is my Main.java source code file

[10, 20, 30, 40, 50, 60, 70, 80]
10

Process finished with exit code 0

The above is IntelliJ’s console output.

Without looking at a piece of source code or a specific error, it would be very difficult to proceed.

  1. In order to isolate the error, could you post a small piece of code that replicates the error and includes the output?
  2. Also, can you post your addFirst() method?
2 Likes
4 
public void addFirst(int item) {
        var node = new Node(item);

        if(isEmpty())
            first = last = node;
        else {
           node.next = first;
           first = node;
        }

        size++;
    }

public int getKthFromTheEnd(int k) {
        if(isEmpty())
            throw new IllegalStateException();
        
        var a = first;
        var b =first;

        for (int i=0; i< k-1;i++) {
            b = b.next;
            if(b == null)
                throw new IllegalArgumentException();
        }

public class Main {
    public static void main(String[] args) {
        var list = new LinkedList();
        list.addFirst(10);
        list.addFirst(20);
        list.addFirst(30);
        list.addFirst(40);
        list.addFirst(50);

        System.out.println(list.getKthFromTheEnd(2));
    }
}

And I got the output: 20
but I had to get “40” as output

5

@Hamid-asna, the output appears to be correct. When I get stuck with a bug, sometimes it helps to write comments and my expected output. Let’s walk through the code that uses the addFirst() method step-by-step:

// output printed as an array
// add first 10
[10]
// add first 20
[20,10]
// add first 30
[30,20,10]
// add first 40
[40,30,20,10]
// add first 50
[50,40,30,20,10]
// get 2nd element from the end
20

Now, let’s add the same numbers, but this time, we’ll use the addLast() method. I think that this may be where the confusion lies.

// Again, output printed as an array
// add last 10
[10]
// add last 20
[10,20]
// add last 30
[10,20,30]
// add last 40
[10,20,30,40]
// add last 50
[10,20,30,40,50]
// get 2nd element from the end
40
2 Likes
6

Yes!, it’s correct but I was not careful. Thank you :pray: :heart_eyes:

1 Like