19. Remove Nth Node From End of List

2020, Dec 05 One min read

1. Description

Given the head of a linked list, remove the nth node from the end of the list and return its head.

2. Example

Example 1

Example 1
Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

Example 2

Input: head = [1], n = 1
Output: []

Example 3

Input: head = [1,2], n = 1
Output: [1]

3. Constraints

The number of nodes in the list is sz.
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

4. Solutions

Two Pointers

n is the number of nodes in head
Time complexity: O(n)
Space complexity: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    ListNode *removeNthFromEnd(ListNode *head, int n) {
        ListNode dummy(0, head);
        ListNode *slow = &dummy, *fast = &dummy;
        for (int i = 0; i < n; ++i) {
            fast = fast->next;
        }

        while (fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next;
        }

        slow->next = slow->next->next;

        return dummy.next;
    }
};

Search

Tags