前言

两题难度还行，不是很难，需要注意一下边界值，第一题是寻常链表，第二题可以用动态规划做。

t1

小红拿到了一个链表，她需要把所有偶数节点合并到该节点前面和它相邻的奇数节点上(新节点权值为两个节点权值之和)，直到剩余的节点无法合并为止。你能帮帮她吗?

示例1

输入

{2,3,4,1,2,2,3}

输出

{2,7,5,3}

说明

对于链表2->3->4->1->2->2->3，先将4合并到3上面，形成2->7->1->2->2->3，然后将2合并到1上面，形成2->7->3->2->3，最后将2合并到3上面，形成2->7->5->3。此时无法合并，合并结束。

思路与代码

在循环中，首先跳过当前节点和后续的所有偶数值节点，直到找到一个奇数值节点或到达链表末尾。

   ListNode mergNode(ListNode head) {
        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode cur = head;
        while(cur != null) {
            while(cur != null && cur.val % 2 == 0) {
                cur = cur.next;
            }
            if(cur == null) break;
            ListNode next = cur.next;
            while(next != null && next.val % 2 == 0) {
                cur.val += next.val;
                next = next.next;
            }
            cur.next = next;
            cur = next;
        }
        return dummy.next;
    }

t2

小红拿到了一个链表。她每次操作会随机选择一个节点，将该节点、该节点下一个节点和该节点上一个节点同时删除。请注意，如果选择的节点是头节点，则不存在上一个节点，若是尾节点，则不存在下一个节点。

小红希望你计算将链表删成空链表的操作次数的期望 1<=n<=10^5

如果你返回的答案和正确答案的相对误差不超过10^-3，则认为你的答案正确。

示例1

输入

3

输出

1.66666667

说明

如果第一次击打最左边或者最右边的弹珠，则还需要一次击打。

如果第一次击打中间的弹珠，则直接打出全部弹珠。答案是1/3* 1+2/3*2=5/3

思路与代码

直接使用动态规划的方式计算了一个级数的期望值，并在最后将结果以8位小数的形式打印出来。

  static double get_expect(int n) {
        if(n == 1 || n == 2) {
            return (double)1;
        }
        double[] f = new double[n + 1];
        f[1] = 1;
        f[2] = 1;
        for(int i = 3;i <= n;i++) {
            f[i] += (double)(i - 2) / i * (1 + f[i - 3]);
            f[i] += (double)2 / i * (1 + f[i - 2]);
        }
        double ans = f[n];
        String str = String.format("%.8f", ans);
        ans = Double.parseDouble(str);
        return ans;
    }

    public static void main(String[] args) {
        int n = 3;
        System.out.println(get_expect(n));
    }
}