題目描述#
https://leetcode.cn/problems/merge-nodes-in-between-zeros/description/
簡單模擬題，熟悉鏈表操作即可
我的方法#
依次遍歷即可。原地做法，不增加新的節點。
設置兩個指針，分別為 cur_node 和 prev_node
在原鏈表上，依次遍歷。如果下一個結點的 value 不是 0，則將下一個結點的 value 值加到 cur_node 的 value 值裡，並刪除那個結點。
直到下一個結點的 value 值等於 0 為止。此時，更新 cur_node 和 prev_node 的值。
當某個值為 0 的結點的 next 為 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; // nonzero
ListNode* cur_node = head->next; // nonzero
ListNode* prev_node = head->next; // nonzero
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. 快慢指針
我個人比較喜歡這種做法，感覺更優雅一些