小红的链表扩展

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

思路

给定一个链表，要求在每两个相邻节点之间插入一个值为 0 的新节点。

做法非常直接：从头节点开始遍历链表，对于每个节点 cur（只要 cur.next 存在），创建一个值为 0 的新节点，将其插入 cur 和 cur.next 之间，然后将指针跳到新节点的下一个节点（即原来的 cur.next），继续处理。

样例演示

输入链表 {1,2,3,1}：

cur = 1，在 1 和 2 之间插入 0，链表变为 1 → 0 → 2 → 3 → 1，cur 跳到 2。
cur = 2，在 2 和 3 之间插入 0，链表变为 1 → 0 → 2 → 0 → 3 → 1，cur 跳到 3。
cur = 3，在 3 和 1 之间插入 0，链表变为 1 → 0 → 2 → 0 → 3 → 0 → 1，cur 跳到 1。
cur = 1，cur.next 为空，结束。

输出 {1,0,2,0,3,0,1}，与预期一致。

代码

C++
Java

class Solution {
public:
    ListNode* insert0(ListNode* head) {
        ListNode* cur = head;
        while (cur && cur->next) {
            ListNode* zero = new ListNode(0);
            zero->next = cur->next;
            cur->next = zero;
            cur = zero->next;
        }
        return head;
    }
};

import java.util.*;

public class Solution {
    public ListNode insert0 (ListNode head) {
        ListNode cur = head;
        while (cur != null && cur.next != null) {
            ListNode zero = new ListNode(0);
            zero.next = cur.next;
            cur.next = zero;
            cur = zero.next;
        }
        return head;
    }
}

复杂度分析

时间复杂度： $O(n)$ ，其中 $n$ 为链表长度。遍历一次链表，每个原始节点处理一次。
空间复杂度： $O(n)$ 。需要创建 $n - 1$ 个新节点插入链表中。