[LeetCode] 19. Remove Nth Node From End of List

Table of Contents

Description

Given the head of a linked list, remove the $n^{th}$ node from the end of the list and return its head.

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]

Constraints:

• The number of nodes in the list is sz.
• $1 \leq sz \leq 30$
• $0 \leq Node.val \leq 100$
• $1 \leq n \leq sz$

Follow up: Could you do this in one pass?

Approach

We can traverse the linked list to store all nodes in an array. Then, we can easily access the node to be removed by its index. And finally, we can connect the previous node to the next node of the one to be removed.

Solution

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function (head, n) {
  // nodes array stores all nodes of the linked list
  let currentNode = head,
    nodes = [];

  // Traverse the linked list and push each node into nodes array
  while (currentNode) {
    nodes.push(currentNode);
    currentNode = currentNode.next;
  }

  // Determine the node to remove, which is the nth node from the end
  let nodeToRemove = nodes[nodes.length - n];
  // Determine the node before the one to remove
  let previousNode = nodes[nodes.length - n - 1];

  // If previousNode is undefined, it means nodeToRemove is the head node
  if (!previousNode) return nodeToRemove.next;

  // Connect previousNode with the node after nodeToRemove
  previousNode.next = nodeToRemove.next;

  return head;
};

Complexity Analysis

Time Complexity

The time complexity is $O(sz)$, where $sz$ is the number of nodes in the linked list. This is because we traverse the entire list to store the nodes in an array and then access the node to be removed.

Space Complexity

The space complexity is $O(sz)$, where $sz$ is the number of nodes in the linked list. This is due to the storage of all nodes in an array.