merge

[题目链接](https://www.nowcoder.com/practice/ffc1db76f741475b90af47dfb3c84ebf)

思路

问题分析

给出一个长度为 的链表 ，链表是优美的当且仅当：

1. 若 ，如 存在，则 ；
2. 若 ，如 存在，则 。

即相邻两个节点不能同时为零，也不能同时为非零——整个链表必须是 和非零值严格交替出现的。

我们可以将一个节点与相邻节点合并，合并后的值取两者的较大值。求使链表变为优美链表所需的最少合并次数。

关键观察：合并 = 缩短连续同类段

把原链表按"零"和"非零"分成若干极大连续段（run）。例如：

$$

由于极大连续段已经天然地在零段与非零段之间交替排列，所以每一段恰好可以作为结果链表中的一个节点，段内所有元素合并为一个节点：

• 零段合并后的值为 （全是 取 还是 ）；
• 非零段合并后的值为段内最大值（为正数，满足非零条件）。

这样得到的新链表自然满足 和非零交替出现的优美条件。

为什么不能做得更好？

能否拆分某一段以获得更多的分组？不行。如果一个零段 试图拆成多个零节点，它们相邻且全为零，违反条件 1。类似地，非零段也不能拆分。因此，分组数 = 极大连续段数就是最优解。

算法

遍历链表，统计极大连续段的个数 。每当当前节点的"是否为零"状态与前一个节点不同时，段数加 。答案为 。

复杂度

• 时间复杂度：，一次遍历链表即可。
• 空间复杂度：，只需常数个变量。

代码

[sol-C++]

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    int merge(ListNode* a) {
        int n = 0, groups = 0;
        bool prevZero = false;
        bool first = true;
        for (ListNode* cur = a; cur; cur = cur->next) {
            n++;
            bool isZero = (cur->val == 0);
            if (first || isZero != prevZero) {
                groups++;
                prevZero = isZero;
                first = false;
            }
        }
        return n - groups;
    }
};

[sol-Java]

import java.util.*;

public class Solution {
    /**
     * @param a ListNode类
     * @return int整型
     */
    public int merge(ListNode a) {
        int n = 0, groups = 0;
        boolean prevZero = false;
        boolean first = true;
        for (ListNode cur = a; cur != null; cur = cur.next) {
            n++;
            boolean isZero = (cur.val == 0);
            if (first || isZero != prevZero) {
                groups++;
                prevZero = isZero;
                first = false;
            }
        }
        return n - groups;
    }
}