AlgoViz
HomeLinked List

Remove Nth node from the back of the LL

Medium

Two pointers, n apart

Problem

Given the head of a singly linked list and an integer n. Remove the n^th node from the back of the linked List and return the head of the modified list. The value of n will always be less than or equal to the number of nodes in the linked list.

In simple words

Send one pointer n steps ahead, then move both together — when it hits the end, you're at the target.

The idea

Advance one pointer n nodes ahead, then move both together until it reaches the end — the trailing pointer is now just before the node to remove. A dummy node in front of the head removes the special case of deleting the head itself.

The trick

  • Use a dummy head; deleting the first node then needs no special branch.
  • The gap must be exactly n for the trailing pointer to land on the predecessor.
  • One pass, O(1) space.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

1
2
3
4
5
2
0
1
2
3
4
5

Step 1 of 2. Here's the example — linkedList = 1 -> 2 -> 3 -> 4 -> 5, n = 2 Values: 1, 2, 3, 4, 5, 2.

1/2
Optimal
timeO(n)spaceO(1)
1fast = head2repeat n times: fast = fast.next3if fast == null: return head.next   // remove head4slow = head5while fast.next: slow = slow.next; fast = fast.next6slow.next = slow.next.next7return head

Input

array
[1, 2, 3, 4, 5, 2]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
list = 1 -> 2 -> 3 -> 4 -> 5, n = 2
Output:
1 -> 2 -> 3 -> 5
Explanation:
The 2nd from the end (4) is removed.

Example 2

Input:
list = 1 -> 2, n = 1
Output:
1
Explanation:
Drop the last node.

Example 3

Input:
list = 1 -> 2 -> 3, n = 3
Output:
2 -> 3
Explanation:
Remove the head.

Constraints

  • 1 <= number of nodes in the Linked List <= 10^5
  • 0 <= ListNode.val <= 10^4
  • 1 <= n <= number of nodes in the Linked List.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.