[LeetCode] 19. Remove Nth Node From End of List

Problem

Given the head of a linked list, remove the $n^{th}$ node from the end of the list and return its head.

BCR(Best Conceivable Runtime)

To finding the $n^{th}$ node from the end of the list, we need to go through the list from the end at least $n^{th}$ times. Because, each node in signly linked list only points next node of itself, so we can not access the $n^{th}$ node in $O(1)$. Therefore the best conceivable runtime is $O(n)$.

Solution 1

Basic idea of the first solution is that the $n^{th}$ from the end of the list is same with the $(sz-n+1)^{th}$ nodes from the start. So If we know the size of the list, we can find the $n^{th}$ from the end of the list. we can compute the size of the list easily by going through the list until we meet null.

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null || n <= 0) return head;
        ListNode ptr = head;
        // compute the size of the list
        int sz = 0;
        while (ptr != null) {
            ptr = ptr.next;
            sz++;
        }
        if (n > sz) return head;
        if (n == sz) return head.next;
        ptr = head;
        for (int i = 1; i <= sz-n-1; i++) {
            ptr = ptr.next;
        }
        ptr.next = ptr.next.next;
        return head;
    }
}

And then, we can remove the $(sz-n+1)^{th}$ node from the first easily. In case of n ==sz, we don't need to go through the list. the time complexity above the code is $O(sz)$ and the space complexity is $O(1)$ because it only saves the pointer of node and some integers.

Solution 2

Basic idea of the second solution is using two pointers. There are two pointers slow and fast that is n ahead of slow. By doing this, slow will points the $n^{th}$ node from the end of the list when fast points null. But it is easier to remove the $n^{th}$ node when easy points the $(n-1)^{th}$ node. So we only go through the list until fast.next != null, not fast == null. Now we can remove the $n^{th}$ node from the end of the list by one pass.

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode slow = head, fast = head;
        for (int i = 0; i < n; i++) fast = fast.next;
        if (fast == null) return head.next;
        while (fast.next != null) {
            slow = slow.next; fast = fast.next;
        }
        slow.next = slow.next.next;
        return head;
    }
}

The time complexity is still same with solution 1, But it is more faster than that because it only goes in one pass.

Thoughts

I think two pointer problem is hardest in the world. Solution 1 was so easy but it was so hard to make a idea of solution 2. I need to solve some two pointer problems to get used to two pointer techniques.