反转偶数长度组的节点 图解题解

这道题到底在问什么

输入

head = [5,2,6,3,9,1,7,3,8,4]

输出

[5,6,2,3,9,1,4,8,3,7]

输入

head = [1,2]

输出

[1,2]

最优解：一步一步想明白

1. 3记住这一句:切组的长度是 1,2,3,4 一路递增,但真正决定反不反转的,是每一组实际分到几个节点,偶数就翻、奇数就留。下面从第一个节点开始,一组一组走。
2. 4目标:偶数组反转先看这条链表,从左到右 8 个节点,值分别是 5,2,6,3,9,1,7,3,末尾的 null 表示到头了。开始之前先约定两个记号:i 表示当前这一组从哪个位置起,现在是 0;size 表示当前这一组的目标长度,从 1 起步。接下来每处理完一组,size 就加 1,i 跳到下一组的开头。
3. 5四组长度 1,2,3,2先在脑子里把组划出来。第一个节点 5 自己是第一组,长度 1;接着 2 和 6 是第二组,长度 2;再接着 3,9,1 是第三组,长度 3;第四组本该要 4 个,可后面只剩 7 和 3 两个节点了,那就分到 2 个,长度 2。所以四组的长度是 1,2,3,2。注意最后一组被截短了,它的长度要按实际分到的算。
4. 6第一组开工轮到第一组。当前 i=0,这一组的目标长度 size=1。组头先落在位置 0 的节点 5 上。接下来要从这里往后数,看这一组实际能分到几个节点。
5. 7组区间 [0,0]从位置 0 往后数 1 个,组尾停在位置 0 的节点 5。这一组的实际长度就是 1,正好等于目标长度。
6. 8奇数组保留这一组的实际长度是 1,奇数。规则是奇数组一个都不动,原样保留。于是把这 1 个节点直接定下来,标成已完成。第一组只有一个节点,天然没法反转,也符合规则。下面 size 加 1,i 跳到位置 1,处理下一组。
7. 9第二组开工轮到第二组。当前 i=1,这一组的目标长度 size=2。组头先落在位置 1 的节点 2 上。接下来要从这里往后数,看这一组实际能分到几个节点。
8. 10组区间 [1,2]从位置 1 往后数 2 个,组尾停在位置 2 的节点 6。这一组的实际长度就是 2,正好等于目标长度。
9. 11偶数组待反转这一组的实际长度是 2,偶数,要反转。反转的办法很直接:左指针 l 指组头位置 1,右指针 r 指组尾位置 2,把 l 和 r 的值交换,然后 l 右移、r 左移,一直到它们相遇或错过。这一组只有两个节点,交换一次就完事。
10. 12交换 (1,2)把位置 1 和位置 2 两个节点的值交换。交换以后,位置 1 变成 6,位置 2 变成 2。接着 l 往右、r 往左一走就相遇了,这一组的反转到此结束。
11. 13偶数组已翻这一组反转完毕。反转前这一段的值是 2,6,反转后变成 6,2。把这 2 个节点定下来,标成已完成。下面 size 加 1,i 跳到位置 3,接着往后处理。
12. 14第三组开工轮到第三组。当前 i=3,这一组的目标长度 size=3。组头先落在位置 3 的节点 3 上。接下来要从这里往后数,看这一组实际能分到几个节点。
13. 15组区间 [3,5]从位置 3 往后数 3 个,组尾停在位置 5 的节点 1。这一组的实际长度就是 3,正好等于目标长度。
14. 16奇数组保留这一组的实际长度是 3,奇数。规则是奇数组一个都不动,原样保留。于是把这 3 个节点直接定下来,标成已完成。值和顺序都不变。下面 size 加 1,i 跳到位置 6,处理下一组。
15. 17第四组开工轮到第四组。当前 i=6,这一组的目标长度 size=4。组头先落在位置 6 的节点 7 上。接下来要从这里往后数,看这一组实际能分到几个节点。
16. 18组区间 [6,7]从位置 6 往后数,本想数够 4 个,可到 7 就是最后一个节点了,后面没有了。这一组实际只分到 2 个,组尾停在位置 7。这就是最后一组被截短的情形,它的实际长度是 2,而不是目标的 4。
17. 19实际长度说了算这里是最容易出错的一步。这一组目标长度 size 是 4,是偶数;但它实际只分到 2 个节点。到底反不反转,要看实际长度 2 的奇偶,而不是看目标 4。实际长度 2 是偶数,所以它照样要反转。本例目标 4 和实际 2 恰好同为偶数,判断碰巧一致;可要是最后一组实际分到 3 个,3 是奇数就不该反转,这时还拿目标 4 去判反而会把该留的翻了。所以判奇偶永远认实际长度。
18. 20偶数组待反转这一组的实际长度是 2,偶数,要反转。反转的办法很直接:左指针 l 指组头位置 6,右指针 r 指组尾位置 7,把 l 和 r 的值交换,然后 l 右移、r 左移,一直到它们相遇或错过。这一组只有两个节点,交换一次就完事。
19. 21交换 (6,7)把位置 6 和位置 7 两个节点的值交换。交换以后,位置 6 变成 3,位置 7 变成 7。接着 l 往右、r 往左一走就相遇了,这一组的反转到此结束。
20. 22偶数组已翻这一组反转完毕。反转前这一段的值是 7,3,反转后变成 3,7。把这 2 个节点定下来,标成已完成。下面 size 加 1,i 跳到位置 8,接着往后处理。
21. 23答案 5,6,2,3,9,1,3,7四组全部处理完了。第一组长度 1 奇数没动;第二组长度 2 偶数,5 后面的 2,6 翻成 6,2;第三组长度 3 奇数没动;最后一组长度 2 偶数,7,3 翻成 3,7。整条链表最终是 5,6,2,3,9,1,3,7,这就是答案。
22. 24偶数才翻再回放一遍。判断反不反转,自始至终只看一条:这一组实际分到的节点个数是奇是偶。第一组 1 个、第三组 3 个,都是奇数,原样保留;第二组 2 个、第四组 2 个,都是偶数,组内反转。特别记住最后一组:它目标是 4 个,实际只分到 2 个,按实际长度 2 是偶数,照样要翻。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
from string import *
from operator import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def reverseEvenLengthGroups(self, head: Optional[ListNode]) -> Optional[ListNode]:
        vals = []
        cur = head
        while cur:
            vals.append(cur.val)
            cur = cur.next
        i, size = 0, 1
        while i < len(vals):
            j = min(len(vals), i + size)
            if (j - i) % 2 == 0:
                vals[i:j] = reversed(vals[i:j])
            i = j
            size += 1
        dummy = ListNode(0)
        cur = dummy
        for v in vals:
            cur.next = ListNode(v)
            cur = cur.next
        return dummy.next

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
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* reverseEvenLengthGroups(ListNode* head) {
        vector<int> vals;
        for (auto p = head; p; p = p->next) vals.push_back(p->val);
        int i = 0, size = 1, n = vals.size();
        while (i < n) {
            int j = min(n, i + size);
            if ((j - i) % 2 == 0) reverse(vals.begin() + i, vals.begin() + j);
            i = j;
            ++size;
        }
        ListNode dummy(0), *cur = &dummy;
        for (int v : vals) { cur->next = new ListNode(v); cur = cur->next; }
        return dummy.next;
    }
};

import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    public ListNode reverseEvenLengthGroups(ListNode head) {
        ArrayList<Integer> vals = new ArrayList<>();
        for (ListNode p = head; p != null; p = p.next) vals.add(p.val);
        int i = 0, size = 1;
        while (i < vals.size()) {
            int j = Math.min(vals.size(), i + size);
            if ((j - i) % 2 == 0) {
                for (int l = i, r = j - 1; l < r; l++, r--) {
                    int t = vals.get(l);
                    vals.set(l, vals.get(r));
                    vals.set(r, t);
                }
            }
            i = j;
            size++;
        }
        ListNode dummy = new ListNode(0), cur = dummy;
        for (int v : vals) { cur.next = new ListNode(v); cur = cur.next; }
        return dummy.next;
    }
}

复杂度

面试官可能追问