Problem 246701 · easy · Level 02 Linear Data Structures

k-th Value From the End

linked list · two pointers

Given the head of a singly linked list and an integer k, return the value of the k-th node from the end, where k = 1 means the last node. If k is less than 1 or larger than the length, return None.

Examples

Input:  head = 1 -> 2 -> 3 -> 4 -> 5, k = 2
Output: 4

Input:  head = 1 -> 2 -> 3, k = 3
Output: 1

Constraints

  • 0 <= number of nodes <= 10**4
  • -10**4 <= k <= 10**4
  • Target: O(n) time, O(1) extra space, in one pass (no counting pass first)

Goals

  • Use two pointers separated by a fixed gap
  • Answer a from-the-end question in a single pass
Starting Python…