Remove Nth Node From End of List
Problem
https://leetcode.com/problems/remove-nth-node-from-end-of-list/
Given the head of a linked list, remove the n:sup:`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 <= sz <= 300 <= Node.val <= 1001 <= n <= sz
Follow up: Could you do this in one pass?
Pattern
Linked List, Two Pointers
Solution
First, iterate through the linked list and get its length \(l\). The problem reduces to remove the \(i = l - n\) th node.
There are 3 cases for deleting a node in a linked list:
1. Beginnning: Set head to head.next.
2. Middle: Set prev.next = prev.next.next where prev is \(i - 1`th
node.
3. End: Set ``prev.next = None``\) where prev is the penultimate node. Note
that this is equivalent to the middle case since Node = prev.next.next.
Code
from __future__ import annotations
from typing import List
class ListNode:
"""Node in a linked list.
"""
def __init__(self, val: int, next: ListNode | None = None):
self.val = val
self.next = next
def to_list(self) -> List[int]:
list = []
while self is not None:
list.append(self.val)
self = self.next
return list
@classmethod
def from_list(cls, list: List[int]) -> ListNode | None:
head: ListNode | None = None
prev_node: ListNode | None = None
for el in list:
node = ListNode(el)
if head is None:
head = node
elif prev_node is not None:
prev_node.next = node
prev_node = node
prev_node = node
return head
def removeNthFromEnd(head: ListNode | None, n: int) -> ListNode | None:
"""Remove the nth node from the end of the linked list starting at ``head``.
"""
node = head
length = 0
while node is not None:
length += 1
node = node.next
i = length - n
# remove the first node
if i == 0:
head = head.next
return head
# remove a middle node
prev = head
for i in range(i - 1):
prev = prev.next
prev.next = prev.next.next
return head
Test
>>> from remove_nth_node_from_end_of_list__approach_1 import ListNode, removeNthFromEnd
>>> head = ListNode.from_list([1, 2, 3, 4, 5])
>>> removeNthFromEnd(head, 2).to_list()
[1, 2, 3, 5]
>>> head = ListNode.from_list([1])
>>> print(removeNthFromEnd(head, 1))
None
>>> head = ListNode.from_list([1, 2])
>>> removeNthFromEnd(head, 1).to_list()
[1]