🎨Now live: Try our Free AI Image Generation Feature

Intuition
The problem requires removing the nth node from the end of a linked list. To do this effectively, we need to know the position of the node relative to the start of the list. This can be achieved by calculating the total length of the list and using it to find the nth node from the end.
Approach
- Calculate Length: Traverse the list to determine its total length.
- Dummy Node: Introduce a dummy node to handle edge cases, such as removing the head of the list.
- Find Target Node: Traverse the list again to find the node just before the nth node from the end.
- Remove Node: Adjust the pointers to remove the target node.
- Return Modified List: Return the head of the modified list, skipping the dummy node.
Complexity
Time Complexity:
O(L), where L is the length of the list. We traverse the list twice: once to calculate its length and once to locate the node to be removed.
Space Complexity:
O(1). We use a constant amount of additional space.
Code
C++
/**
* Definition for singly-linked list.
* 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) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
int length = 0;
ListNode* curr = head;
// Calculate the length of the list
while (curr != nullptr) {
length++;
curr = curr->next;
}
// Use a dummy node to simplify edge cases
ListNode dummy(0, head);
curr = &dummy;
// Find the node just before the one we want to remove
for (int i = 0; i < length - n; ++i) {
curr = curr->next;
}
// Remove the nth node from the end
if (curr->next != nullptr) {
curr->next = curr->next->next;
}
return dummy.next;
}
};
Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
length = 0
curr = head
# Calculate the length of the list
while curr:
length += 1
curr = curr.next
# Use a dummy node to simplify edge cases
dummy = ListNode(0, head)
curr = dummy
# Find the node just before the one we want to remove
for _ in range(length - n):
curr = curr.next
# Remove the nth node from the end
if curr.next:
curr.next = curr.next.next
return dummy.next
Java
/**
* Definition for singly-linked list.
* public 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) {
int length = 0;
ListNode curr = head;
// Calculate the length of the list
while (curr != null) {
length++;
curr = curr.next;
}
// Use a dummy node to simplify edge cases
ListNode dummy = new ListNode(0);
dummy.next = head;
curr = dummy;
// Find the node just before the one we want to remove
for (int i = 0; i < length - n; i++) {
curr = curr.next;
}
// Remove the nth node from the end
if (curr.next != null) {
curr.next = curr.next.next;
}
return dummy.next;
}
}
JavaScript
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} n
* @return {ListNode}
*/
var removeNthFromEnd = function(head, n) {
let length = 0
let curr = head
while(curr!=null) {
length++
curr = curr.next
}
let index = 0
let dummy = new ListNode(0, head)
curr = dummy
while(curr!=null) {
if(index==(length-n)) {
curr.next = curr.next ? curr.next.next : null
break
}
index++
curr = curr.next
}
return dummy.next
};