後ろからN番目のNodeを削除する問題です。
時間計算量O(N)、空間計算量O(N)の例
パッと思いついた方法は、Nodeを配列に変換して削除する1つ手前のListNode::nextを書き換える方法でした。
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
std::vector<ListNode*> nodes;
ListNode dummy_head = ListNode(0, head);
ListNode* current = &dummy_head;
while (current != nullptr) {
nodes.emplace_back(current);
current = current->next;
}
nodes[nodes.size() - n - 1]->next = 1 < n
? nodes[nodes.size() - n + 1]
: nullptr;
return dummy_head.next;
}
};dummy_headを使用しているのは先頭のNodeを削除するケース (n = size) の考慮です。
空間計算量O(1)の例
業務内で、O(N)のメモリ確保もケチりたい場面には出会ったことがないですが、調べたらO(1)で済む方法があったので載せておきます。
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode dummy_head = ListNode(0, head);
ListNode* fast = &dummy_head;
for (int i = 0; i < n; i++) {
fast = fast->next;
}
ListNode* slow = &dummy_head;
while (fast->next != nullptr) {
fast = fast->next;
slow = slow->next;
}
slow->next = slow->next->next;
return dummy_head.next;
}
};- fastを先頭からN番目まで進める
- fastをN番目から末尾まで進める(同時にslowを先頭から同じ数だけ進める)
- slowが後ろからN+1番目のNodeを指しているため、slow::nextを書き換える
もう少し具体的に考えてみると以下のイメージになります。(Nodeのsize=5, N=2の場合)
ちなみに、dummy_headを使わない場合は、fastのnullチェックが必要です。(上記の例でいう N=5の場合)
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* fast = head;
for (int i = 0; i < n; i++) {
fast = fast->next;
}
if (fast == nullptr) {
return head->next;
}
ListNode* slow = head;
while (fast->next != nullptr) {
fast = fast->next;
slow = slow->next;
}
slow->next = slow->next->next;
return head;
}
};
以上です！