Find the Kth Node From the End of a Linked List
Solve this Problemhead of a singly linked list and an integer k, return the value of the kth node counted from the end of the list (1-indexed, so k = 1 is the last node). Return -1 if k is larger than the list.
A singly linked list can only be walked forward, so "distance from the end" isn't something a single pointer knows on its own. The optimal solution fixes that with a head startHead Start (k-Gap) TechniqueAdvance one pointer k steps before starting the second one. The k-node gap between them stays constant as both move together, so when the leading pointer runs out of list, the trailing pointer is exactly k nodes from the end.: let fast move k steps ahead of slow, then walk both together — the fixed gap between them means slow lands exactly on the answer the moment fast falls off the end.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ number of nodes in head ≤ 10⁴ - ◆
-10⁹ ≤ node value ≤ 10⁹ - ◆
k is 1-indexed from the end — k = 1 means the last node - ◆
If k is greater than the number of nodes, return -1
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
| 1 | class Solution { |
| 2 | public int kthNodeFromEnd(Node head, int k) { |
| 3 | Node fast = head; |
| 4 | for (int i = 0; i < k; i++) { |
| 5 | if (fast == null) { |
| 6 | return -1; |
| 7 | } |
| 8 | fast = fast.next; |
| 9 | } |
| 10 | Node slow = head; |
| 11 | while (fast != null) { |
| 12 | slow = slow.next; |
| 13 | fast = fast.next; |
| 14 | } |
| 15 | return slow.val; |
| 16 | } |
| 17 | } |
| 18 |
2fast starts at head — it needs to move k steps ahead of slow before slow even starts moving.
Approach & Solutions
Brute Force — Count Length, Then Traverse to (length - k)
GoodWalk the list once to count its length. If k is bigger than that length, it's out of range. Otherwise, the kth-from-end node sits at 0-indexed position (length - k) from the front — walk there in a second pass. Correct, but it needs the length before it can even start looking.
O(n)O(1)1// Node definition used in this problem:
2// class Node {
3// int val;
4// Node next;
5// }
6
7class Solution {
8 public int kthNodeFromEnd(Node head, int k) {
9 int count = 0;
10 Node curr = head;
11 while (curr != null) {
12 count++;
13 curr = curr.next;
14 }
15 if (k > count) {
16 return -1;
17 }
18 curr = head;
19 for (int i = 0; i < count - k; i++) {
20 curr = curr.next;
21 }
22 return curr.val;
23 }
24}Optimal — Two Pointers, k Apart, Single Pass
OptimalMove fast k steps ahead of slow first (returning -1 immediately if the list runs out before that). Then advance both one step at a time until fast reaches null. The k-node gap between them stays fixed the whole way, so when fast runs off the end, slow is sitting exactly k nodes from the end — found in a single pass.
O(n)O(1)1// Node definition used in this problem:
2// class Node {
3// int val;
4// Node next;
5// }
6
7class Solution {
8 public int kthNodeFromEnd(Node head, int k) {
9 Node fast = head;
10 for (int i = 0; i < k; i++) {
11 if (fast == null) {
12 return -1;
13 }
14 fast = fast.next;
15 }
16 Node slow = head;
17 while (fast != null) {
18 slow = slow.next;
19 fast = fast.next;
20 }
21 return slow.val;
22 }
23}