Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Remove Nth Node From End of List solution and explanation

MediumLinked ListTwo Pointers6 min read52.4% acceptanceUpdated 9 Apr 2026
Asked atBroadcomSymantecQualcommTinkoffMetaMorgan Stanley
+12 moreAmazonAccentureJosh TechnologyGoogleMicrosoftBloombergAppleWalmart LabsTiktokTCSYandexOracle
Practise Remove Nth Node From End of List
7:09
Remove Nth Node from End of List - Oracle Interview Question - Leetcode 19NeetCode · 7:09 · 292K viewsWatch on YouTube
9 more videos on this problem
  1. Remove Nth Node from End of List - Oracle Interview Question - Leetcode 19NeetCode · 7:09 · 292K views
  2. LeetCode Remove Nth Node From End of List Solution Explained - JavaNick White · 5:39 · 51K views
  3. Remove nth node from end of Linked List (LeetCode 19) | A very very easy solutionNikhil Lohia · 14:45 · 26K views
  4. Remove Nth Node from End of List - Leetcode 19 - Linked Lists (Python)Greg Hogg · 7:42 · 17K views
  5. LeetCode 19: Remove Nth Node From End of List - Interview Prep Ep 58Fisher Coder · 12:42 · 10K views
  6. LEETCODE 19 (JAVASCRIPT) | REMOVE NTH NODE FROM END OF LISTAndy Gala · 10:51 · 5K views
  7. Remove Nth Node From End of List | LeetCode 19 | 2 PointersAbstracted Away · 4:33 · 2K views
  8. Remove Nth Node From End Of List - LeetCode 19 - JavaScriptAlgoJS · 4:32 · 1K views
  9. Remove Nth Node From End of List - LeetCode 19 - Python (Iterative and Recursive!)Deepti Talesra · 20:06 · 1K views
  10. Remove Nth Node From End of List Python Solution - LeetCode #19Professor Oakes · 4:09 · 610 views

The problem

Given the head of a linked list, remove the nth 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 <= 30
  • 0 <= Node.val <= 100
  • 1 <= n <= sz

Follow up: Could you do this in one pass?

Approach overview

Problem Overview: You are given the head of a singly linked list and an integer n. The task is to remove the nth node from the end of the list and return the updated head. The challenge is handling this in a single traversal while safely updating pointers in a linked list.

Approach 1: Two-Pass Technique (O(n) time, O(1) space)

The simplest strategy is to first determine the length of the linked list. Traverse the list once and count how many nodes it contains. Once you know the total length L, the node to remove is at position L - n from the start. Perform a second traversal to reach the node just before this position, then update its next pointer to skip the target node.

This approach works well because pointer updates are straightforward when you know the exact index to remove. Edge cases require attention, especially when the head itself must be removed (n == L). A common trick is introducing a dummy node before the head so that pointer manipulation remains consistent. Time complexity is O(n) due to two full traversals, and space complexity is O(1) since no additional data structures are required.

Approach 2: One-Pass Technique with Fast and Slow Pointers (O(n) time, O(1) space)

The optimal solution uses the two pointers technique. Maintain two pointers called fast and slow. First move the fast pointer n steps ahead of slow. This creates a fixed gap between them. Then move both pointers forward together until fast reaches the end of the list.

Because the gap remains constant, when fast reaches the last node, slow will be positioned right before the node that must be removed. Updating slow.next = slow.next.next removes the target node in constant time. A dummy head node simplifies cases where the first element must be removed. This approach finishes the task in a single traversal with O(n) time complexity and O(1) auxiliary space.

Recommended for interviews: The fast and slow pointer solution is what most interviewers expect. It demonstrates strong understanding of pointer manipulation and efficient traversal patterns in a linked list. The two-pass method is still valuable to explain first because it shows clear reasoning about list length and index transformation. Then follow with the one-pass approach to demonstrate optimization using the two pointers technique.

Approach 1: Two-Pass Technique

Two-Pass Technique

This approach involves two passes through the linked list to find the node that needs to be removed. In the first pass, compute the length of the list. In the second pass, remove the (Len - n + 1)th node from the start of the list by maintaining a pointer to manage node deletions properly.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def getLength(self, head: ListNode) -> int:
        length = 0
        while head:
            length += 1
            head = head.next
        return length

    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        length = self.getLength(head)
        dummy = ListNode(0, head)
        current = dummy
        for _ in range(length - n):
            current = current.next
        current.next = current.next.next
        return dummy.next
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Solution {
    public int getLength(ListNode head) {
        int length = 0;
        while (head != null) {
            length++;
            head = head.next;
        }
        return length;
    }

    public ListNode removeNthFromEnd(ListNode head, int n) {
        int length = getLength(head);
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode current = dummy;
        for (int i = 0; i < length - n; i++) {
            current = current.next;
        }
        current.next = current.next.next;
        return dummy.next;
    }
}
#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

int getLength(ListNode* head) {
    int length = 0;
    while (head) {
        length++;
        head = head->next;
    }
    return length;
}

ListNode* removeNthFromEnd(ListNode* head, int n) {
    int length = getLength(head);
    ListNode* dummy = new ListNode();
    dummy->next = head;
    ListNode* current = dummy;
    for (int i = 0; i < length - n; ++i) {
        current = current->next;
    }
    ListNode* toDelete = current->next;
    current->next = current->next->next;
    delete toDelete;
    ListNode* newHead = dummy->next;
    delete dummy;
    return newHead;
}
function ListNode(val, next) {
    this.val = (val===undefined ? 0 : val);
    this.next = (next===undefined ? null : next);
}

var getLength = function(head) {
    let length = 0;
    while (head !== null) {
        length++;
        head = head.next;
    }
    return length;
};

var removeNthFromEnd = function(head, n) {
    let length = getLength(head);
    let dummy = new ListNode(0, head);
    let current = dummy;
    for (let i = 0; i < length - n; i++) {
        current = current.next;
    }
    current.next = current.next.next;
    return dummy.next;
};
#include <stdio.h>
#include <stdlib.h>

struct ListNode {
    int val;
    struct ListNode *next;
};

int getLength(struct ListNode *head) {
    int length = 0;
    while (head) {
        length++;
        head = head->next;
    }
    return length;
}

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    int length = getLength(head);
    struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
    dummy->next = head;
    struct ListNode* current = dummy;
    for (int i = 0; i < length - n; i++) {
        current = current->next;
    }
    struct ListNode *toDelete = current->next;
    current->next = current->next->next;
    free(toDelete);
    struct ListNode *newHead = dummy->next;
    free(dummy);
    return newHead;
}
public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val = 0, ListNode next = null) {
        this.val = val;
        this.next = next;
    }
}

public class Solution {
    public int GetLength(ListNode head) {
        int length = 0;
        while (head != null) {
            length++;
            head = head.next;
        }
        return length;
    }

    public ListNode RemoveNthFromEnd(ListNode head, int n) {
        int length = GetLength(head);
        ListNode dummy = new ListNode(0, head);
        ListNode current = dummy;
        for (int i = 0; i < length - n; i++) {
            current = current.next;
        }
        current.next = current.next.next;
        return dummy.next;
    }
}

This Python implementation uses a similar approach by leveraging a helper function to calculate the length of the linked list. A dummy node is used for straightforward logic when adjusting pointers. After finding the correct position, it links the node before and after the nth node from the end, effectively removing it.

Complexity

Time Complexity: O(L), with L representing the total nodes in the list, since it traverses the list twice.
Space Complexity: O(1), maintaining a constant space usage outside of the provided list structure.

Try this approach in the editor

Approach 2: One-Pass Technique with Fast and Slow Pointers

One-Pass Technique with Fast and Slow Pointers

This approach uses two pointers, fast and slow. Begin by moving the fast pointer n steps ahead. Then move both pointers simultaneously until fast reaches the end. This provides the correct position to remove the nth node from the end efficiently in one go.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummy = ListNode(0, head)
        fast = slow = dummy
        for _ in range(n + 1):
            fast = fast.next
        while fast:
            fast = fast.next
            slow = slow.next
        slow.next = slow.next.next
        return dummy.next
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode fast = dummy;
        ListNode slow = dummy;
        for (int i = 0; i <= n; i++) {
            fast = fast.next;
        }
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }
}
#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode* dummy = new ListNode(0, head);
    ListNode* fast = dummy;
    ListNode* slow = dummy;
    for (int i = 0; i <= n; ++i) {
        fast = fast->next;
    }
    while (fast) {
        fast = fast->next;
        slow = slow->next;
    }
    ListNode* toDelete = slow->next;
    slow->next = slow->next->next;
    delete toDelete;
    ListNode* newHead = dummy->next;
    delete dummy;
    return newHead;
}
function ListNode(val, next) {
    this.val = (val===undefined ? 0 : val);
    this.next = (next===undefined ? null : next);
}

var removeNthFromEnd = function(head, n) {
    let dummy = new ListNode(0);
    dummy.next = head;
    let fast = dummy;
    let slow = dummy;
    for (let i = 0; i <= n; i++) {
        fast = fast.next;
    }
    while (fast !== null) {
        fast = fast.next;
        slow = slow.next;
    }
    slow.next = slow.next.next;
    return dummy.next;
};
#include <stdio.h>
#include <stdlib.h>

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
    dummy->next = head;
    struct ListNode *fast = dummy, *slow = dummy;
    for (int i = 0; i <= n; i++) {
        fast = fast->next;
    }
    while (fast) {
        fast = fast->next;
        slow = slow->next;
    }
    struct ListNode* toDelete = slow->next;
    slow->next = slow->next->next;
    free(toDelete);
    struct ListNode* newHead = dummy->next;
    free(dummy);
    return newHead;
}
public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val = 0, ListNode next = null) {
        this.val = val;
        this.next = next;
    }
}

public class Solution {
    public ListNode RemoveNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode fast = dummy, slow = dummy;
        for (int i = 0; i <= n; i++) {
            fast = fast.next;
        }
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }
}

In Python, the one-pass solution engages two pointers, advancing fast first by n nodes. Following this lead, fast and slow traverse concurrently, ensuring slow's position is optimal for the necessary node removal.

Complexity

Time Complexity: O(L), dictated by single-traversal efficiency via double pointers.
Space Complexity: O(1), facilitated through limited storage overhead.

Try this approach in the editor

Approach 3: Fast and Slow Pointers

We define two pointers fast and slow, both initially pointing to the dummy head node of the linked list.

Next, the fast pointer moves forward n steps first, then fast and slow pointers move forward together until the fast pointer reaches the end of the linked list. At this point, the node pointed to by slow.next is the predecessor of the n-th node from the end, and we can delete it.

The time complexity is O(n), where n is the length of the linked list. The space complexity is O(1).

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
    const dummy = new ListNode(0, head);
    let fast = dummy;
    let slow = dummy;
    while (n--) {
        fast = fast.next;
    }
    while (fast.next) {
        slow = slow.next;
        fast = fast.next;
    }
    slow.next = slow.next.next;
    return dummy.next;
}
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
	dummy := &ListNode{0, head}
	fast, slow := dummy, dummy
	for ; n > 0; n-- {
		fast = fast.Next
	}
	for fast.Next != nil {
		slow, fast = slow.Next, fast.Next
	}
	slow.Next = slow.Next.Next
	return dummy.Next
}
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
        let dummy = ListNode(0)
        dummy.next = head
        var fast: ListNode? = dummy
        var slow: ListNode? = dummy
        for _ in 0..<n {
            fast = fast?.next
        }
        while fast?.next != nil {
            fast = fast?.next
            slow = slow?.next
        }
        slow?.next = slow?.next?.next
        return dummy.next
    }
}
// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
//   #[inline]
//   fn new(val: i32) -> Self {
//     ListNode {
//       next: None,
//       val
//     }
//   }
// }
impl Solution {
    pub fn remove_nth_from_end(head: Option<Box<ListNode>>, n: i32) -> Option<Box<ListNode>> {
        let mut dummy = Some(Box::new(ListNode { val: 0, next: head }));
        let mut slow = &mut dummy;
        let mut fast = &slow.clone();
        for _ in 0..=n {
            fast = &fast.as_ref().unwrap().next;
        }
        while fast.is_some() {
            fast = &fast.as_ref().unwrap().next;
            slow = &mut slow.as_mut().unwrap().next;
        }
        slow.as_mut().unwrap().next = slow.as_mut().unwrap().next.as_mut().unwrap().next.take();
        dummy.unwrap().next
    }
}
# Definition for singly-linked list.
# class ListNode
#     attr_accessor :val, :next
#     def initialize(val = 0, _next = nil)
#         @val = val
#         @next = _next
#     end
# end
# @param {ListNode} head
# @param {Integer} n
# @return {ListNode}
def remove_nth_from_end(head, n)
    dummy = ListNode.new(0, head)
    fast = slow = dummy
    while n > 0
        fast = fast.next
        n -= 1
    end
    while fast.next
        slow = slow.next
        fast = fast.next
    end
    slow.next = slow.next.next
    return dummy.next
end
/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val = 0, $next = null) {
 *         $this->val = $val;
 *         $this->next = $next;
 *     }
 * }
 */
class Solution {
    /**
     * @param ListNode $head
     * @param Integer $n
     * @return ListNode
     */
    function removeNthFromEnd($head, $n) {
        $dummy = new ListNode(0, $head);
        $fast = $slow = $dummy;
        for ($i = 0; $i < $n; $i++) {
            $fast = $fast->next;
        }
        while ($fast->next !== null) {
            $fast = $fast->next;
            $slow = $slow->next;
        }
        $slow->next = $slow->next->next;
        return $dummy->next;
    }
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Two-Pass Technique

Time Complexity: O(L), with L representing the total nodes in the list, since it traverses the list twice.
Space Complexity: O(1), maintaining a constant space usage outside of the provided list structure.

One-Pass Technique with Fast and Slow Pointers

Time Complexity: O(L), dictated by single-traversal efficiency via double pointers.
Space Complexity: O(1), facilitated through limited storage overhead.

Fast and Slow Pointers–

Complexity analysis

ApproachTimeSpaceWhen to Use
Two-Pass Length CountingO(n)O(1)Best for clarity and when computing list length first simplifies reasoning
One-Pass Fast and Slow PointersO(n)O(1)Preferred interview solution when a single traversal is required

Frequently asked questions

Is Remove Nth Node From End of List easy or hard?

Remove Nth Node From End of List is categorized as a Medium difficulty problem. The logic is straightforward once you understand two-pointer traversal, but handling edge cases like removing the head node or lists with a single element can make it tricky.

Remove Nth Node From End of List Python/Java solution

Python and Java implementations typically follow the fast and slow pointer strategy with a dummy head node. The dummy node simplifies edge cases such as removing the first element. Both implementations run in O(n) time and O(1) extra space.

How to solve Remove Nth Node From End of List in O(n)?

Use the two-pointer technique. Advance a fast pointer n steps ahead of a slow pointer, then move both pointers forward until fast reaches the end of the list. At that moment, slow will point to the node before the target. Updating slow.next removes the nth node from the end in O(n) time and O(1) space.

What is the best approach for Remove Nth Node From End of List?

The most efficient approach uses fast and slow pointers. Move the fast pointer n steps ahead, then advance both pointers together until fast reaches the end. The slow pointer will stop right before the node that needs removal. This method completes in O(n) time and O(1) space with only one traversal.

Is Remove Nth Node From End of List asked at Google/Amazon/Meta?

Remove Nth Node From End of List is a common linked list interview problem reported in interviews at companies like Amazon, Google, and Meta. It tests pointer manipulation, edge case handling, and understanding of the two-pointer technique in singly linked lists.

What data structure is used in Remove Nth Node From End of List?

The problem operates on a singly linked list. The solution relies on pointer manipulation to traverse nodes and update next references. The optimal algorithm also applies the two-pointer technique to maintain a fixed gap between nodes during traversal.

What is the time complexity of Remove Nth Node From End of List?

Both common solutions run in O(n) time where n is the number of nodes in the linked list. The two-pass approach traverses the list twice to compute length and remove the node. The optimized fast–slow pointer technique completes the task in a single traversal with O(1) extra space.

Comments

Next problem · similarSwapping Nodes in a Linked ListMedium
Now write it yourselfClose this page and solve Remove Nth Node From End of List in the editor, without looking.
Practise Remove Nth Node From End of List