# 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.

Could you do this in one pass?

## Analysis

#### 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.

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

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

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

``````public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
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:

``````/**
* 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);
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;
}
}
``````