Program for n'th node from the end of a linked list

Easy

Problem

Return the nth node from the end of the list, or null if the list has fewer than n nodes.

Example 1

Input:  1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9, n = 2
Output: the node with value 8

Also asked as: Program for n’th node from the end of a Linked List

Test cases

Case 1

Input:    [1,2,3,4,5,6,7,8,9], 2
Expected: 8

Case 2

Input:    [1,2,3], 1
Expected: 3

Case 3

Input:    [1,2,3], 3
Expected: 1

Case 4

Input:    [1,2], 5
Expected: null

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Two pointers, n apart

Time O(n)Space O(1)

Advance a lead pointer n nodes, then move lead and trail together until lead falls off the end.

function nthFromEnd(head, n) {
let lead = head;
for (let i = 0; i < n; i++) { if (!lead) return null; lead = lead.next; }
let trail = head;
while (lead) { lead = lead.next; trail = trail.next; }
return trail;
}