Redirecting to
NADOS

Kth Node From End Of Linked List

  Prev   Next

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

1. You are given a partially written LinkedList class.
2. Here is a list of existing functions:
     2.1 addLast - adds a new element with given value to the end of Linked List
     2.2. display - Prints the elements of linked list from front to end in a single line. 
     All elements are separated by space.
    2.3. size - Returns the number of elements in the linked list.
    2.4. removeFirst - Removes the first element from Linked List. 
    2.5. getFirst - Returns the data of first element. 
    2.6. getLast - Returns the data of last element. 
    2.7. getAt - Returns the data of element available at the index passed. 
    2.8. addFirst - adds a new element with given value in front of linked list.
    2.9. addAt - adds a new element at a given index.
    2.10. removeLast - removes the last element of linked list.
    2.11. removeAt - remove an element at a given index
3. You are required to complete the body of kthFromLast function. The function should be an iterative function and should return the kth node from end of linked list. Also, make sure to not use size data member directly or indirectly (by calculating size via making a traversal). k is a 0-based index. Assume that valid values of k will be passed.
4. Input and Output is managed for you.
Input Format 
Input is managed for you
Output Format 
Output is managed for you
Question Video
Constraints 
1. Size property should not be used directly or indirectly
2. Constant time, single traversal is expected
3. Iterative solution, (not recursion) is expected
Sample Input 
addLast 10
getFirst
addLast 20
addLast 30
getFirst
getLast
getAt 1
addLast 40
kthFromEnd 3
getLast
addLast 50
removeFirst
getFirst
removeFirst
removeFirst
kthFromEnd 0
removeFirst
removeFirst
getFirst
quit
Sample Output 
10
10
30
20
10
40
20
50
List is empty


  • Editorial

    The problem deals with finding the element at the kTh index from the end of the linked list. Say for example we have a list, 1 -> 2 -> 3 -> 4 -> 5, and we are given k = 2 then we would get our result as 3.

    There can be many approaches to solve this problem The first approach is the two pointer approach. The intuition behind this approach is to keep a fast pointer (or ahead pointer) which points at node k distance ahead of the current node. This step ensures that when the fast pointer reaches the last node of the list then the current node lies at our desired position. To have better clarity let us suppose that our fast pointer has reached the end node, and as we also know that this pointer is k steps ahead of the current node which implies that our current node is (k + 1) steps from the end or at the kTh index from the end of the list and hence the current node is our desired node.

    Another approach would be to deduce the formula in mathematical terms for the node at the kTh index from the end. For that let us suppose that the length of the list is n and we wish to find the node at index k from the end, then this is the same as finding the node at (n - 1 - k)Th index from the beginning of the list. Say for example our list is 1 -> 2 -> 3 -> 4 -> 5, and we are given k = 2 then by our formula we would get (5 - 1 - 2) = 2nd Index which is equal to the third node which is our desired node, hence our formula is verified.

    Below is the implementation for Approach 1 in Java: 

    public int kthFromLast(int k){
                                    Node slow = head;
                                    Node fast = head;
                                    for(int i = 0; i < k; i++){
                                    fast = fast.next;
                                    } 
                                    while(fast != tail){
                                    slow = slow.next;
                                    fast = fast.next;
                                    } 
                                    return slow.data;
                                }

    java false

    Dry Run

    Input List: 1 -> 2 -> 3 -> 4 -> 5

    K Value: 2

    Output: 3

    Initially, slow = 1st Node and fast = 1st Node

    For loop

    1. I = 0 =>fast = 2nd Node

    2. I = 1 =>fast = 3rd Node

    3. I = 2 == K => loop breaks

    While loop

    1. First Iteration

    fast ( = 3rd Node)  != tail ( = 5th Node)

    slow = 2nd Node

    fast = 4th Node

    2. Second Iteration

    fast ( = 4th Node)  != tail ( = 5th Node)

    slow = 3rd Node

    fast = 5th Node

    3. Third Iteration

    fast ( = 5th Node)  == tail ( = 5th Node)

    Loop Breaks

    Returnslow.data = 3 (Result)

    Time Complexity: O(n)

    The time complexity for the function is linear as the traversal of the linked list is involved.

    Space Complexity: O(1)

    The space complexity for the function is constant as we have only used referenced variables in our algorithm.

  • Asked in Companies
  • Related Topics






Video Solution

Code Solution

Run
 
Run
Id Name