Dare2Solve
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.
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.
O(1). We use a constant amount of additional space.
/**
* 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;
}
};
# 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
/**
* 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;
}
}
/**
* 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
};