Leetcode 19 Solution

Leetcode Question Link

https://leetcode.com/problems/remove-nth-node-from-end-of-list

Thinking Process

This is a very basic coding question, but there are two cases we need to handle:

1. Removing the head node.
2. Removing a node after the head.

Although it is perfectly doable to implement the two logics, there is a better way. We’d like to transform the question to simplify it!

The simpliest way to do that would be adding a dummy head node in the front, and then remove the Nth node in the new list from the last (it could never be the head). Last, we return the second node in the list.

By doing this, we eliminate the concern of removing the head node, so that you only need to handle the second case, which is a lot easier and makes the code a lot simpler.

Time & Space Complexity

Assuming N is the size of the list

• Time complexity: O(N)
• Space complexity: O(1)

Solution

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* p = head;

        int len = 0;

        while (p)
        {
            p = p->next;
            len++;
        }

        if (n > len || n <= 0)
            return head;

        ListNode* prev = NULL;
        p = head;

        for (int i = 1; i <= len - n; i++)
        {
            prev = p;
            p = p->next;
        }

        if (prev != NULL)
        {
            prev->next = p->next;
            return head;
        }
        else
        {
            return p->next;
        }
    }
};

Learning

• Think of the dummy head trick whenever you are tackling a list issue.