19. Remove Nth Node From End of List

---

My Solution

Solution 1

The Key Idea for Solving This Coding Question

C++ Code

/**
 * 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) {
        int len = 0;
        ListNode *it = head;
        while (it != nullptr) {
            ++len;
            it = it->next;
        }

        int target = len - n;
        ListNode *dummy = new ListNode(), *prev = dummy, *curr = head;
        dummy->next = head;
        for (int i = 0; i < target; ++i) {
            prev = prev->next;
            curr = curr->next;
        }

        prev->next = curr->next;
        delete curr;

        head = dummy->next;
        delete dummy;
        return head;
    }
};

Time Complexity

$O(n)$

$n$ is the number of nodes in the linked list referred by head.

Space Complexity

$O(1)$

Solution 2:

The Key Idea for Solving This Coding Question

DFS. Recursion. Post order traversal.
Solve this coding question in one pass.

C++ Code 1

/**
 * 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 *dummy = new ListNode();
        dummy->next = head;

        dfs(dummy, head, n);
        head = dummy->next;
        delete dummy;

        return head;
    }

private:
    void dfs(ListNode *prev, ListNode *head, int &n) {
        if (head == nullptr) {
            return;
        }

        dfs(head, head->next, n);

        --n;
        if (n == 0) {
            prev->next = head->next;
            delete head;
            return;
        }
    }
};

C++ Code 2

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

struct Solution {
public:
    ListNode *removeNthFromEnd(ListNode *head, int n) {
        ListNode *dummy = new ListNode();

        dummy->next = dfs(head, n);

        head = dummy->next;
        delete dummy;

        return head;
    }

private:
    ListNode *dfs(ListNode *head, int &n) {
        if (head == nullptr) {
            return nullptr;
        }

        head->next = dfs(head->next, n);
        --n;
        if (n == 0) {
            ListNode *x = head->next;
            delete head;
            return x;
        }

        return head;
    }
};

Time Complexity

$O(n)$

$n$ is the number of nodes in the linked list referred by head.

Space Complexity

$O(n)$

Solution 3:

The Key Idea for Solving This Coding Question

Use two pointers and iteration to solve this coding question in one pass.

C++ Code

/**
 * 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 *dummy = new ListNode(), *it1 = dummy, *it2 = head;
        dummy->next = head;

        while (n > 0) {
            it2 = it2->next;
            --n;
        }
        while (it2 != nullptr) {
            it1 = it1->next;
            it2 = it2->next;
        }

        ListNode *x = it1->next;
        it1->next = it1->next->next;
        delete x;

        head = dummy->next;
        delete dummy;
        return head;
    }
};

Time Complexity

$O(n)$

$n$ is the number of nodes in the linked list referred by head.

Space Complexity

$O(1)$

Miscellaneous