</>Ali · LeetCode
#0019·MediumLinked Lists

Remove Nth Node From End of List

LeetCode #19 · Medium · Linked Lists · C++ solution with worked-out approach and complexity analysis.

View on LeetCodeSource on GitHub

Approach

Two-Pass Algorithm (Calculate Size)

Key insight

To find the nth node from the end, we can first determine the length of the list, L. Then, the problem becomes removing the (L - n + 1)th node from the beginning.

Strategy

  1. 1Traverse the list to calculate its total size.
  2. 2Handle the special case where we need to remove the head (size - n ==
  3. 3Traverse the list again to the node just before the target node (index
  4. 4Update the next pointer of the predecessor to skip the target node.
Time
O(L)
we traverse the list twice.
Space
O(1)
we only use a few pointers.
Problem description(from LeetCode)

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

Examples

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

Constraints

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

C++ Solution

solution.cpp
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) {
    if (head == nullptr || head->next == nullptr) return nullptr;

    int size = 0;
    ListNode *temp = head;
    while (temp != nullptr) {
      size++;
      temp = temp->next;
    }

    if (size - n == 0) return head->next;

    temp = head;
    int index = 1;
    while (temp->next != nullptr) {
      if (index == size - n) {
        temp->next = temp->next->next;
        break;
      } else {
        temp = temp->next;
      }
      index++;
    }

    return head;
  }
};

More Linked Lists problems