Limited Time Offer:Up to 20% off Hello Interview Premium

⌘K

Tutor

Linked List

Remove Nth Node From End of List

medium

DESCRIPTION (inspired by 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.

Example 1:

Input: n = 2

Output:

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

Example 2:

Input: n = 5

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.

Visualization

Try these examples:


def removeNthFromEnd(head, n):
    # find length
    length = 0
    current = head
    while current:
        length += 1
        current = current.next
    
    target = length - n
    if target == 0:
        return head.next
    
    current = head
    for _ in range(target - 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.

Visualization

Try these examples:


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.

Visualization


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 first advances n nodes, then both pointers advance together until fast reaches the end. In total, fast traverses N nodes and slow traverses N - n nodes, giving us 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.

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.

Visualization


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.

Visualization


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.

Visualization


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!

Visualization


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`)

Implementation

Here's the complete dummy node approach that elegantly handles all edge cases:

Solution

def removeNthFromEnd(head, n):
    # Create dummy node to handle edge case of removing head
    dummy = ListNode(0)
    dummy.next = head
    fast = dummy
    slow = dummy
    
    # Move fast pointer n steps ahead to create n-node gap
    for i in range(n):
        fast = fast.next
    
    # Move both pointers until fast reaches end
    # When fast is at last node, slow will be at node before target
    while fast.next is not None:
        fast = fast.next
        slow = slow.next
    
    # Remove the nth node from end by skipping it
    slow.next = slow.next.next
    
    return dummy.next  # Return head of modified list

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.

Visualization

Try these examples:


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

Test Your Knowledge

Complexity Analysis

Time Complexity: 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.

Space Complexity: 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.

Mark as read

Next: Reorder List

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

Unlock Premium Coding Content

Interactive algorithm visualizations

Guided Practice

Recent interview questions

Learn More

Reading Progress

On This Page

Solutions

1. Find the Length of the List

2. Use Two Pointers

3. Dummy Node

Implementation

Code

Linked List

Remove Nth Node From End of List

DESCRIPTION (inspired by Leetcode.com)

Solutions

1. Find the Length of the List

2. Use Two Pointers

3. Dummy Node

Removing the Head Node

Implementation

Code

Test Your Knowledge

Complexity Analysis

Comments

Questions

Learn

Links

Legal

Contact