Remove Nth Node From End of List

Remove Nth Node From End of List is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Two Pointers pattern, in the Fixed Separation (Nth Node from End) subpattern.

Problem statement

Given the head of a linked list, remove the nth node from the end of the list and return its head.

Example 1:

Input: head = [1,2,3,4,5], n = 2 Output: [1,2,3,5]

Example 2:

Input: head = [1], n = 1 Output: []

Example 3:

Input: head = [1,2], n = 1 Output: [1]

Constraints:

- The number of nodes in the list is sz.

- 1 <= sz <= 30

- 0 <= Node.val <= 100

- 1 <= n <= sz

Follow up: Could you do this in one pass?

Topics and companies

Topics: Linked List, Two Pointers.

Reported in interviews at Facebook, Amazon, Microsoft, Bloomberg, Apple.

How to practise Remove Nth Node From End of List on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(sz), where sz is the number of nodes in the list. Each node is visited at most twice: once to advance the fast pointer and once to build the result vector. time and O(sz), for the output vector<int> and for the temporary linked list built from the input vector. space.

Open Remove Nth Node From End of List in the code editor, or read the Remove Nth Node From End of List editorial for a worked solution with its approach and complexity analysis.

Where Remove Nth Node From End of List sits in the DSA pattern sheet

• Two Pointers pattern guide
• Fixed Separation (Nth Node from End) subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Remove Nth Node From End of List

Other problems that use the same Fixed Separation (Nth Node from End) and Two Pointers techniques:

• Delete the Middle Node of a Linked List — Medium, same subpattern
• Middle of the Linked List — Easy, same subpattern
• Backspace String Compare — Easy, same pattern
• Boats to Save People — Medium, same pattern
• Container With Most Water — Medium, same pattern
• Crawler Log Folder — Easy, same pattern