Skip to content
AI360Xpert
Back to Linked List
Medium

Remove Nth Node From End of List

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

Examples

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

Constraints

  • The number of nodes in the list is sz.
  • 1 <= sz <= 30
  • 0 <= Node.val <= 100
  • 1 <= n <= sz

Approach

First, do one pass to count the total number of nodes in the linked list. Then, calculate the index of the node to remove from the beginning (length - n). Do a second pass to reach the node right before the one we want to remove, and update its `next` pointer.

Complexity Analysis

Time Complexity
O(n)
Space Complexity
O(1)

This requires traversing the list twice.

Solution.java
class Solution {    public ListNode removeNthFromEnd(ListNode head, int n) {        int length = 0;        ListNode curr = head;        while (curr != null) {            length++;            curr = curr.next;        }                if (length == n) {            return head.next;        }                curr = head;        for (int i = 1; i < length - n; i++) {            curr = curr.next;        }                curr.next = curr.next.next;        return head;    }}