2074. Reverse Nodes in Even Length Groups #

题目 #

给定链表头结点 head。

链表中的结点按照 按顺序 划分为若干非空组。这些非空组的长度构成一个自然数序列 {1, 2, 3, 4, ...}。一个组的长度就是组中分配到的结点数目。换言之：

结点 1 分配给第一组
结点 2 分配给第二组
结点 4、5、6 分配给第三组，以此类推

注意，最后一组的长度可能小于或等于 1 + 倒数第二组的长度。

反转每个 偶数长度 组中的结点，并返回修改后链表的头结点 head。

思路 #

代码 #

class Solution {
    public void reverseList(ListNode beforeHead, ListNode tail) {
        /** (beforeHead, tail] 要求 beforeHead != tail */
        if (beforeHead == tail) return;
        ListNode afterTail = tail.next;
        ListNode prev = afterTail, cur = beforeHead.next, temp = cur.next;
        while (cur != afterTail) {
            cur.next = prev;
            prev = cur;
            cur = temp;
            if (temp != afterTail) temp = temp.next;
        }
        beforeHead.next = tail;
    }
    public ListNode reverseEvenLengthGroups(ListNode head) {
        ListNode sentinel = new ListNode(-1, head);
        /** interval 标识正在考察那一段链表结点 */
        int interval = 1;
        /** 确定待考察区间的前驱结点 beforeHead 和 尾结点 tail */
        ListNode beforeHead = sentinel, tail = sentinel;
        /** 若链表发生翻转，tail 指向的结点不再位于区间末尾。新的尾结点是翻转前的 before.next 结点，用 ptr 变量暂存这一结点。*/
        ListNode ptr = null;
        /** 若 tail 遇到了 null 指针，结束遍历 */
        while (tail != null) {
            /** 统计区间的实际长度 */
            int length = 0;
            /** 覆盖了 tail 处于正常结点和空结点两种情况 */
            for (int i=0; i<interval && tail.next != null; i++) {
                tail = tail.next;
                length += 1;
            }
            /** 判断是否要翻转区间 (beforeHead, tail]，如果是则执行 */
            ptr = beforeHead.next;
            if (length % 2 == 0) reverseList(beforeHead, tail);
            /** 继续考虑下一段区间 */
            beforeHead = tail = length % 2 == 0 ? ptr : tail;
            interval += 1;
        }
        return head;
    }
}