Friedrich Ewald My Personal Website

Leetcode: Remove nth node from end of list

Given the head of a linked list, remove the nth element from the end of the list and return the head of the list. As a follow-up, this should be done with one iteration. The most obvious solution is to count the number of elements in the list in one iteration. This is necessary, because we don’t know initially how long the list is. Then iterate over the list again and once the index is reached, set pointer = pointer.next. This way the nth element is skipped. However, there is a more elegant way to achieve this. We can set up two pointers, both at the head of the list. We move the first pointer and increment a counter. When the counter reaches n, we start moving the second pointer as well. Once the first pointer reaches the end of the list we simply set the second pointer to the next position and we’re done. There is one special case: When the element that should be removed is the first element. Because we have a pointer to head and return head in the end, this would be discarded. A quick solution is to create a temporary node and point it to the head. Then do the operation as described above. In the end return pre_head.next which points to the new (or old) head. The __str__ and __repr__ methods are small helper methods that I added for easier debugging.

from typing import List, Optional

# Definition for singly-linked list.
class ListNode:
  def __init__(self, val=0, next=None):
    self.val = val
    self.next = next
  
  def __str__(self) -> str:
    """
    Helper to print results to command line.
    """
    s = f"{self.val}"
    if self.next is not None:
      s += f", {self.next}"
    return s
  
  def __repr__(self) -> str:
    """
    Helper for debugging
    """
    return f"<{self.val}>"

class Solution:
  def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
    # Insert dummy element in front of the head so that we can refer to it later
    pre_head = ListNode(-999, head)
    curr = pre_head
    ptr = pre_head
    dist = 0

    while curr.next is not None:
      if dist == n:
        ptr = ptr.next
      else:
        dist += 1
      curr = curr.next
    
    ptr.next = ptr.next.next

    return pre_head.next


if __name__ == '__main__':
  s = Solution().removeNthFromEnd
  print(s(ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5))))), 2), [1,2,3,5])
  print(s(ListNode(1, ListNode(2)), 1), [1])
  print(s(ListNode(1), 1), [])
  print(s(ListNode(1, ListNode(2)), 1), [1])
Runtime: 37 ms, faster than 88.56% of Python3 online submissions for Remove Nth Node From End of List. Memory Usage: 13.9 MB, less than 20.39% of Python3 online submissions for Remove Nth Node From End of List.


About the author

is an experienced Software Engineer with a Master's degree in Computer Science. He started this website in late 2015, mostly as a digital business card. He is interested in Go, Python, Ruby, SQL- and NoSQL-databases, machine learning and AI and is experienced in building scalable, distributed systems and micro-services at multiple larger and smaller companies.