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

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

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