DSA Visualizations | Hello Interview

Remove Nth Node From End of List

DESCRIPTION (credit Leetcode.com)

Given a reference head of type ListNode that is the head node of a singly linked list and an integer n, write a function that removes the n-th node from the end of the list and returns the head of the modified list.

Note: n is guaranteed to be between 1 and the length of the list. If n is the length of the list, the head of the list should be removed.

EXAMPLES

Example 1:

input:

output:

Explanation: The 2nd to last node is removed from the list.

Example 2:

input:

output:

Explanation: The 5th to last node is the head node, so it is removed.

Solutions

In order to remove the n-th node from the end of the list, we first need to locate the node right before it.

For example, if our list is [5, 4, 3, 2, 1] and n = 2, then we need to remove the 2nd node from the end with value 2. In order to do so, we first need to locate the node right before it, with value 3.

If we have a pointer to that node current, we can delete node 2 by setting current.next = current.next.next, which removes node 2 from the list (as no nodes point to it).

Here are a 3 solutions to this problem, each of which approach the problem of locating the node right before the n-th node from the end in a different way.

1. Find the Length of the List

The first approach is to traverse the list to find its length. Once we know the length of the list, we can find the node right before the n-th node from the end by traversing length - n - 1 nodes from the head.


def removeNthFromEnd(head, n):
  length = 0
  current = head
  while current:
    length += 1
    current = current.next

  # special case: removing head
  if n == length:
    return head.next

  current = head
  for _ in range(length - n - 1):
    current = current.next

  current.next = current.next.next
  return head

remove nth node from end of list

0 / 11

We have to handle the special case when n is equal to the length of the list, which requires removing the head node. This needs to be handled separately because head does not have a node right before it to locate. Instead, when n == length, we can remove the head node by returning head.next directly.

Time Complexity: O(N), where N is the number of nodes in the list. We traverse the list once to find the length of the list, and another time to find the node right before the n-th node from the end. Both traversals take O(N) time.

Space Complexity: O(1). We only use a constant amount of extra space for the pointers, regardless of the number of nodes in the list.

2. Use Two Pointers

Instead of traversing the list once to find its length, we can use two pointers, fast and slow that both start at head. To start, fast advances n nodes ahead of slow. Then both pointers advance one node at a time until fast reaches the last node in the list.

At this point, slow will point to the node right before the n-th node from the end, and we can remove the n-th node by setting slow.next = slow.next.next.


def removeNthFromEnd(head, n):
  fast = slow = head
  for _ in range(n):
    fast = fast.next
  
  # special case: removing head
  if not fast:
    return head.next
  
  while fast.next:
    fast = fast.next
    slow = slow.next
  
  slow.next = slow.next.next
  return head

remove nth node from end of list

0 / 7

Like before, we have to handle the special case when n is equal to the length of the list. Since we don't know the length of the list, we can't detect this case by comparing the two values directly. Instead, if fast is None after advancing n nodes, we know that n is equal to the length of the list, and we can remove the head node by returning head.next directly.


def removeNthFromEnd(head, n):
  fast = slow = head
  for _ in range(n):
    fast = fast.next
  
  # special case: removing head
  if not fast:
    return head.next
  
  while fast.next:
    fast = fast.next
    slow = slow.next
  
  slow.next = slow.next.next
  return head

remove nth node from end of list

0 / 7

Handling of special case when removing the head of the list. (n = 5)

Time Complexity: O(N), where N is the number of nodes in the list. The fast pointer traverses the entire list once, taking O(N) time. The slow pointer traverses n nodes after the fast pointer, where n is the input parameter. This takes O(N) time in the worst case.

Space Complexity: O(1). We only use a constant amount of extra space for the pointers, regardless of the number of nodes in the list.

3. Dummy Node

In the two above approaches, we need special logic to handle removing the head node because the head node does not have a node right before it to locate.

We can avoid this special case by introducing a dummy node that points to the head of the list. The dummy node allows us to treat every node, including the head, as if it has a preceding node. With the dummy node established, we can again use the two-pointer approach to find the node right before the n-th node from the end.


def removeNthFromEnd(head, n):
  dummy = ListNode(0)
  dummy.next = head

  fast, slow = dummy, dummy
  for _ in range(n):
    fast = fast.next

  while fast.next:
    fast = fast.next
    slow = slow.next

  # remove nth node from end
  slow.next = slow.next.next
  return dummy.next

remove nth node from end of list

0 / 1

Introducing a dummy node

Both the fast and slow pointers start at the dummy node, and like before, fast advances n nodes ahead of slow. Then both pointers advance one node at a time until fast reaches the last node in the list.


def removeNthFromEnd(head, n):
  dummy = ListNode(0)
  dummy.next = head

  fast, slow = dummy, dummy
  for _ in range(n):
    fast = fast.next

  while fast.next:
    fast = fast.next
    slow = slow.next

  # remove nth node from end
  slow.next = slow.next.next
  return dummy.next

initialize dummy node

0 / 6

Introducing a dummy node

At this point, slow will point to the node right before the n-th node from the end, and we can remove the n-th node by setting slow.next = slow.next.next, and return dummy.next as the head of the modified list.


def removeNthFromEnd(head, n):
  dummy = ListNode(0)
  dummy.next = head

  fast, slow = dummy, dummy
  for _ in range(n):
    fast = fast.next

  while fast.next:
    fast = fast.next
    slow = slow.next

  # remove nth node from end
  slow.next = slow.next.next
  return dummy.next

fast = fast.next, slow = slow.next

0 / 2

Removing the Head Node

With the dummy node, when n is equal to the length of the list, slow still points to the dummy node after both the fast and slow pointers finish advancing.

Now, we can remove the head node by setting slow.next = slow.next.next, and return slow.next as the head of the modified list - which is the exact same logic as removing any other node!


def removeNthFromEnd(head, n):
  dummy = ListNode(0)
  dummy.next = head

  fast, slow = dummy, dummy
  for _ in range(n):
    fast = fast.next

  while fast.next:
    fast = fast.next
    slow = slow.next

  # remove nth node from end
  slow.next = slow.next.next
  return dummy.next

fast = fast.next

0 / 2

Removing the head node (n = 5)

Code

To construct the linked list that is used in the animation below, provide a list of integers nodes. Each integer in nodes is used as the value of a node in the linked list, and the order of the integers in the list will be the order of the nodes in the linked list.

For example, if nodes = [1, 2, 3], the linked list will be 1 -> 2 -> 3.


def removeNthFromEnd(head, n):
  dummy = ListNode(0)
  dummy.next = head

  fast, slow = dummy, dummy
  for _ in range(n):
    fast = fast.next

  while fast.next:
    fast = fast.next
    slow = slow.next

  # remove nth node from end
  slow.next = slow.next.next
  return dummy.next

remove nth node from end of list

0 / 9

Complexity Analysis

Time Complexity: The time complexity of the dummy node approach is O(N), where N is the number of nodes in the list. The fast pointer always traverses the entire list once, taking O(N) time. At worst, when n = 1, the slow pointer traverses to the 2nd to last node, which also takes O(N) time. Removing the n-th node from the end takes O(1) time, so the overall time complexity is O(N).

Space Complexity: The space complexity of the dummy node approach is O(1). We only use a constant amount of extra space for the pointers and allocate one dummy node, regardless of the number of nodes in the list.

Next: Reorder List

Your account is free and you can post anonymously if you choose.

Sort By

Loading comments...

Back to Home

Eliminating Pairs

Overview

Container With Most Water

3-Sum

Triangle Numbers

Pointers as Regions

Move Zeroes

Sort Colors

Trapping Rain Water

Variable-Length

Overview

Longest Substring Without Repeating Characters

Longest Repeating Character Replacement

Fixed-Length

Overview

Maximum Sum of Subarrays of Size K

Max Points You Can Obtain From Cards

Max Sum of Distinct Subarrays Length k

Overview

Can Attend Meetings

Insert Interval

Non-Overlapping Intervals

Merge Intervals

Employee Free Time

Overview

Valid Parentheses

Decode String

Longest Valid Parentheses

Monotonic Stack

Overview

Daily Temperatures

Largest Rectangle in Histogram

Overview

Linked List Cycle

Palindrome Linked List

Remove Nth Node From End of List

Reorder List

Swap Nodes in Pairs

Overview

Apple Harvest (Koko Eating Bananas)

Search in Rotated Sorted Array

Overview

Kth Largest Element in an Array

K Closest Points to Origin

Find K Closest Elements

Merge K Sorted Lists

Introduction

Binary Trees

Overview

Level Order Sum

Rightmost Node

Zigzag Level Order

Maximum Width of Binary Tree

Graphs

Overview

Minimum Knight Moves

Rotting Oranges

01-Matrix

Bus Routes

Overview

Word Search

Solution Space Trees

Subsets

Generate Parentheses

Combination Sum

Topological Sort

Overview

Course Schedule

Course Schedule II

Fundamentals

Solving a Question with Dynamic Programming

Counting Bits

Decode Ways

Maximal Square

Unique Paths

Longest Increasing Subsequence

Word Break

Maximum Profit in Job Scheduling

Overview

Best Time to Buy and Sell Stock

Gas Station

Jump Game

Overview

Implement Trie Methods

Prefix Matching

Overview

Count Vowels in Substrings

Subarray Sum Equals K

Spiral Matrix

Rotate Image

Set Matrix Zeroes

Palindrome Linked List

Reorder List

Remove Nth Node From End of List

DESCRIPTION (credit Leetcode.com)

Note: n is guaranteed to be between 1 and the length of the list. If n is the length of the list, the head of the list should be removed.

EXAMPLES

Example 1:

input:

output:

Explanation: The 2nd to last node is removed from the list.

Example 2:

input:

output:

Explanation: The 5th to last node is the head node, so it is removed.

Solutions

In order to remove the n-th node from the end of the list, we first need to locate the node right before it.

If we have a pointer to that node current, we can delete node 2 by setting current.next = current.next.next, which removes node 2 from the list (as no nodes point to it).

Here are a 3 solutions to this problem, each of which approach the problem of locating the node right before the n-th node from the end in a different way.

1. Find the Length of the List


def removeNthFromEnd(head, n):
  length = 0
  current = head
  while current:
    length += 1
    current = current.next

  # special case: removing head
  if n == length:
    return head.next

  current = head
  for _ in range(length - n - 1):
    current = current.next

  current.next = current.next.next
  return head

remove nth node from end of list

0 / 11

Space Complexity: O(1). We only use a constant amount of extra space for the pointers, regardless of the number of nodes in the list.

2. Use Two Pointers

At this point, slow will point to the node right before the n-th node from the end, and we can remove the n-th node by setting slow.next = slow.next.next.


def removeNthFromEnd(head, n):
  fast = slow = head
  for _ in range(n):
    fast = fast.next
  
  # special case: removing head
  if not fast:
    return head.next
  
  while fast.next:
    fast = fast.next
    slow = slow.next
  
  slow.next = slow.next.next
  return head

remove nth node from end of list

0 / 7


def removeNthFromEnd(head, n):
  fast = slow = head
  for _ in range(n):
    fast = fast.next
  
  # special case: removing head
  if not fast:
    return head.next
  
  while fast.next:
    fast = fast.next
    slow = slow.next
  
  slow.next = slow.next.next
  return head

remove nth node from end of list

0 / 7

Handling of special case when removing the head of the list. (n = 5)

Space Complexity: O(1). We only use a constant amount of extra space for the pointers, regardless of the number of nodes in the list.

3. Dummy Node

In the two above approaches, we need special logic to handle removing the head node because the head node does not have a node right before it to locate.


def removeNthFromEnd(head, n):
  dummy = ListNode(0)
  dummy.next = head

  fast, slow = dummy, dummy
  for _ in range(n):
    fast = fast.next

  while fast.next:
    fast = fast.next
    slow = slow.next

  # remove nth node from end
  slow.next = slow.next.next
  return dummy.next

remove nth node from end of list

0 / 1

Introducing a dummy node


def removeNthFromEnd(head, n):
  dummy = ListNode(0)
  dummy.next = head

  fast, slow = dummy, dummy
  for _ in range(n):
    fast = fast.next

  while fast.next:
    fast = fast.next
    slow = slow.next

  # remove nth node from end
  slow.next = slow.next.next
  return dummy.next

initialize dummy node

0 / 6

Introducing a dummy node


def removeNthFromEnd(head, n):
  dummy = ListNode(0)
  dummy.next = head

  fast, slow = dummy, dummy
  for _ in range(n):
    fast = fast.next

  while fast.next:
    fast = fast.next
    slow = slow.next

  # remove nth node from end
  slow.next = slow.next.next
  return dummy.next

fast = fast.next, slow = slow.next

0 / 2

Removing the Head Node

With the dummy node, when n is equal to the length of the list, slow still points to the dummy node after both the fast and slow pointers finish advancing.

Now, we can remove the head node by setting slow.next = slow.next.next, and return slow.next as the head of the modified list - which is the exact same logic as removing any other node!


def removeNthFromEnd(head, n):
  dummy = ListNode(0)
  dummy.next = head

  fast, slow = dummy, dummy
  for _ in range(n):
    fast = fast.next

  while fast.next:
    fast = fast.next
    slow = slow.next

  # remove nth node from end
  slow.next = slow.next.next
  return dummy.next

fast = fast.next

0 / 2

Removing the head node (n = 5)

Code

For example, if nodes = [1, 2, 3], the linked list will be 1 -> 2 -> 3.


def removeNthFromEnd(head, n):
  dummy = ListNode(0)
  dummy.next = head

  fast, slow = dummy, dummy
  for _ in range(n):
    fast = fast.next

  while fast.next:
    fast = fast.next
    slow = slow.next

  # remove nth node from end
  slow.next = slow.next.next
  return dummy.next

remove nth node from end of list

0 / 9

Complexity Analysis

Next: Reorder List

Your account is free and you can post anonymously if you choose.

Sort By

Loading comments...

BlogBehavioral Interview Examples Interviewing for Experienced SWEs All Blog Posts

Compare UsCompare to Interviewing.io

LinksFAQ Schedule Mock Interviews Pricing Become a Coach Our Coaches Learn System Design Learn DSA Guided Practice Hello Interview Premium

LegalTerms and Conditions Privacy Policy

Contactsupport@hellointerview.com7511 Greenwood Ave North
Unit #4238 Seattle, WA 98103