Problem 205810 · medium · Phase 02 Linear Data Structures

Drop the n-th Node From the End

linked list · two pointers · deletion

Given the head of a singly linked list and an integer n, remove the n-th node from the end (n = 1 is the last node) and return the head of the resulting list.

Examples

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

Input:  head = 1, n = 1
Output: (empty)

Constraints

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

Goals

  • Place a trailing pointer exactly before the node to delete
  • Delete the head with the same code path as any other node
Starting Python…