問題の説明#
https://leetcode.cn/problems/merge-nodes-in-between-zeros/description/
簡単なシミュレーション問題で、リンクリストの操作に慣れていれば大丈夫です。
私の方法#
順番に走査するだけです。インプレースで行い、新しいノードを追加しません。
2 つのポインタを設定します：cur_node と prev_node
元のリンクリスト上で順番に走査します。次のノードの値が 0 でない場合、次のノードの値を cur_node の値に加え、そのノードを削除します。
次のノードの値が 0 になるまで続けます。この時、cur_node と prev_node の値を更新します。
ある値が 0 のノードの次が nullptr の時、アルゴリズムは終了します。この時、cur_node は破棄する必要があります。つまり、prev_node が最後のノードになります。
/**
* 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* mergeNodes(ListNode* head) {
ListNode* new_head = head->next; // 非ゼロ
ListNode* cur_node = head->next; // 非ゼロ
ListNode* prev_node = head->next; // 非ゼロ
while(true){
while (cur_node->next->val != 0) {
cur_node->val += cur_node->next->val;
cur_node->next = cur_node->next->next;
}
// cur_node->next-> val == 0;
prev_node = cur_node;
cur_node = cur_node->next;
if (cur_node->next == nullptr) {
prev_node->next = nullptr;
break;
}
}
return new_head;
}
};
他の方法#
1. 再帰法
2. 速いポインタと遅いポインタ
私はこの方法が個人的に好きで、より優雅だと感じています。