Problem Description#
https://leetcode.cn/problems/merge-nodes-in-between-zeros/description/
A simple simulation problem, just familiarize yourself with linked list operations.
My Approach#
Just traverse sequentially. In-place method, without adding new nodes.
Set two pointers, named cur_node and prev_node
Traverse the original linked list sequentially. If the value of the next node is not 0, add the value of the next node to the value of cur_node, and delete that node.
Continue until the value of the next node is equal to 0. At this point, update the values of cur_node and prev_node.
When the next of a node with a value of 0 is nullptr, the algorithm ends. At this point, cur_node needs to be discarded. In other words, prev_node is the last 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;
}
};
Other Methods#
1. Recursive Method
2. Fast and Slow Pointers
I personally prefer this method, it feels more elegant.