leetcode 2181 合并零之间的结点

题目描述#

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. 快慢指针
我个人比较喜欢这种做法，感觉更优雅一些