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/

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

/**
 * 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

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:

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