Back-To-CP: day 3

15-10-2022

Remove Nth Node From End of List

Another problem that can be solved using two pointers technique.
It can be easily solved if we run a loop and hold all the addresses in an array then just find out the middle point, remove the link between nodes.
But it can be done efficiently using two pointers. Firstly, the fast node is advanced n times, so that the slow pointer will be at the n-1'th position when fast pointer reaches the end.

This however gives an error if the length of the list is equal to n. In which case answer would be null pointer. So, an edge case for checking for list length equal 1 is necessary.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *f = head;
        ListNode *s = head;
        for(int i = 0; i < n ; i++){
            f = f->next;
        }
        if(f == nullptr) {
            return head->next;
        }
        while(f->next != nullptr && f != nullptr) {
            s = s->next;
            f = f->next;
        }

        s->next = s->next->next;
        return head;
    }
};