# Remove Nth Node From End of List

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

**Example:**

```
Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.
```

**Note:**

Given \_n \_will always be valid.

**Follow up:**

Could you do this in one pass?

## Analysis

**Reference**: [https://leetcode.com/problems/remove-nth-node-from-end-of-list/solution/](https://leetcode.com/articles/remove-nth-node-from-end-of-list/)

### Two Pass:

Intuition: Remove the `(L - n + 1) th` node from the beginning in the list , where `L` is the list length. This problem is easy to solve once we found list length `L`.

In the second pass, relink the `next` of `(L - n)` th node to the `(L - n + 2)` the node

**Complexity Analysis**

* Time complexity :O(L)O(L).

  The algorithm makes two traversal of the list, first to calculate list length L and second to find the (L−n) th node. There are 2L- n operations and time complexity isO(L).
* Space complexity :O(1).

  We only used constant extra space.

### One Pass:

Using two pointers, which the first and second pointers are exactly separated by `n` nodes apart, and maintain the constant gap between the two pointers while advancing both of them.

保持一定的距离两个相同速度的pointer，当前方的pointer p1到达末尾时，后方的pointer p2正好是我们需要删除的元素位置的左侧（i - 1）。因为这里是删除操作，因此后方的pointer做一个常规的删除下一个节点的操作即可p2.next = p2.next.next。

**Complexity Analysis**

* Time complexity :O(L).

  The algorithm makes one traversal of the list of L nodes. Therefore time complexity is O(L).
* Space complexity :O(1).

  We only used constant extra space.

## Solution

Two Pass: get length first, then iterate to the node in second pass

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        int length = getLengthOfList(head);
        System.out.println("Length: " + length);
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        for (int i = 0; i < length - n; i++) {
            prev = prev.next;
        }
        prev.next = prev.next.next;
        return dummy.next;
    }
    public int getLengthOfList(ListNode head) {
        int length = 0;
        while (head != null) {
            length++;
            head = head.next;
        }
        return length;
    }
}
```

One Pass: Using two pointers, which first pointer is n nodes ahead of second pointer

```java
public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode first = dummy;
    ListNode second = dummy;
    // Advances first pointer so that the gap between first and second is n nodes apart
    for (int i = 1; i <= n + 1; i++) {
        first = first.next;
    }
    // Move first to the end, maintaining the gap
    while (first != null) {
        first = first.next;
        second = second.next;
    }
    second.next = second.next.next;
    return dummy.next;
}
```

**Two Pointers - Java Preferred Implementation:**

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode p1, p2;
        ListNode dummy = new ListNode(0);    
        dummy.next = head;
        p1 = head;
        p2 = dummy;
        for (int i = 0; i < n; i++) {
            p1 = p1.next;
        }
        while (p1 != null) {
            p1 = p1.next;
            p2 = p2.next;
        }
        p2.next = p2.next.next;
        return dummy.next;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/linked_list/remove-nth-node-from-end-of-list.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.