19. Remove Nth Node From End of List
給定一個鏈表的頭節點，刪除鏈表的倒數第 N 個節點並返回其頭節點。
範例 1：
輸入：head = [1,2], n = 1 輸出：[1]
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]:
# Create a dummy node to simplify edge cases
dummy = ListNode(0)
dummy.next = head
# Initialize two pointers
first = dummy
second = dummy
# Move the first pointer n + 1 steps ahead
for _ in range(n + 1):
first = first.next
# Move both pointers until the first pointer reaches the end
while first:
first = first.next
second = second.next
# Skip the nth node from the end
second.next = second.next.next
# Return the head of the modified list
return dummy.next
16.34MB, 33ms
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) {
// Create a dummy node to simplify edge cases
ListNode* dummy = new ListNode(0);
dummy->next = head;
// Initialize two pointers
ListNode* first = dummy;
ListNode* second = dummy;
// Move the first pointer n + 1 steps ahead
for (int i = 0; i <= n; ++i) {
first = first->next;
}
// Move both pointers until the first pointer reaches the end
while (first != nullptr) {
first = first->next;
second = second->next;
}
// Skip the nth node from the end
ListNode* nodeToRemove = second->next;
second->next = second->next->next;
// Delete the node to avoid memory leak
delete nodeToRemove;
// Store the head of the modified list
ListNode* newHead = dummy->next;
// Delete the dummy node
delete dummy;
return newHead;
}
};
13.34MB, 0ms
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) {
// Create a dummy node to simplify edge cases
let dummy = new ListNode(0);
dummy.next = head;
// Initialize two pointers
let first = dummy;
let second = dummy;
// Move the first pointer n + 1 steps ahead
for (let i = 0; i <= n; i++) {
first = first.next;
}
// Move both pointers until the first pointer reaches the end
while (first !== null) {
first = first.next;
second = second.next;
}
// Skip the nth node from the end
second.next = second.next.next;
// Return the head of the modified list
return dummy.next;
};
50.46MB, 58ms
