700170. Kth from End of Linked List
Kth from End of Linked List
Slug: nth-node-from-end-of-linked-list Difficulty: Easy Id: 700170 Topic Tags: Linked List, Data Structures Company Tags: Flipkart, Morgan Stanley, Accolite, Amazon, OYO Rooms, Samsung, Snapdeal, FactSet, Hike, MAQ Software, Adobe, Qualcomm, Epic Systems, Citicorp, Monotype Solutions
Summary
Given a linked list, the task is to find the kth node from the end of the linked list. This problem involves working with linked lists and understanding how to traverse them efficiently.
Detailed Explanation
The approach for this problem is to use two pointers. One pointer moves at a speed of 1 node per step while the other pointer moves at a speed of (k+1) nodes per step. Initially, both pointers are set to the start of the linked list. When the fast pointer reaches the end of the linked list, the slow pointer will be k nodes away from the end.
Here is a step-by-step breakdown of the solution:
- Create two pointers,
slowandfast, both initially pointing to the head of the linked list. - Move the
fastpointer (k+1) steps ahead. - Move both pointers one step at a time until the
fastpointer reaches the end of the linked list. - The node pointed to by the
slowpointer is the kth node from the end.
Time complexity: O(n), where n is the number of nodes in the linked list. This is because we are traversing the linked list once.
Space complexity: O(1), as we are not using any additional space that scales with the input size.
Optimized Solutions
Java
public class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
ListNode slow = head;
ListNode fast = head;
for (int i = 0; i < k; i++) {
fast = fast.next;
}
while (fast != null) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}