Kth Node From End Of Linked List
1. You are given a partially written LinkedList class.Input Format
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 0based index. Assume that valid values of k will be passed.
4. Input and Output is managed for you.
Input is managed for youOutput Format
Output is managed for youQuestion Video
1. Size property should not be used directly or indirectlySample Input
2. Constant time, single traversal is expected
3. Iterative solution, (not recursion) is expected
addLast 10Sample Output
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
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