LeetCode 2074. 反转偶数长度组的节点（链表）

Michael阿明

发布于 2022-01-07 02:59:35

27100

代码可运行

文章被收录于专栏：Michael阿明学习之路Michael阿明学习之路

运行总次数：0

代码可运行

文章目录
1. 题目
2. 解题

1. 题目

给你一个链表的头节点 head 。

链表中的节点 按顺序 划分成若干非空组，这些非空组的长度构成一个自然数序列（1, 2, 3, 4, …）。一个组的长度就是组中分配到的节点数目。换句话说：

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

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

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

示例 1：

输入：head = [5,2,6,3,9,1,7,3,8,4]
输出：[5,6,2,3,9,1,4,8,3,7]
解释：
- 第一组长度为 1 ，奇数，没有发生反转。
- 第二组长度为 2 ，偶数，节点反转。
- 第三组长度为 3 ，奇数，没有发生反转。
- 最后一组长度为 4 ，偶数，节点反转。

示例 2：

输入：head = [1,1,0,6]
输出：[1,0,1,6]
解释：
- 第一组长度为 1 ，没有发生反转。
- 第二组长度为 2 ，节点反转。
- 最后一组长度为 1 ，没有发生反转。

示例 3：

输入：head = [2,1]
输出：[2,1]
解释：
- 第一组长度为 1 ，没有发生反转。
- 最后一组长度为 1 ，没有发生反转。

示例 4：
输入：head = [8]
输出：[8]
解释：只有一个长度为 1 的组，没有发生反转。

提示：
链表中节点数目范围是 [1, 10^5]
0 <= Node.val <= 10^5

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/reverse-nodes-in-even-length-groups 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

链表反转
prevtail记录前一段的末尾，L, R 记录当前段的起始和结束，nthead 记录下一段的开始

/**
 * Definition for singly-linked list.
 * 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) {
        int num = 1, len = 0;
        ListNode* prevtail = head, *L = NULL, *R = NULL, *cur = head, *nthead = NULL;
        while(cur)
        {
            L = R = cur->next;
            num++;
            int n = num;
            len = 0; 
            while(cur->next && n--)
            {
                len++;
                R = cur->next;
                cur = cur->next;
            }
            nthead = R ? R->next : NULL;
            if(len%2==0)
            {
                if(R)
                    R->next = NULL;//断开，准备反转当前 [L,R]
                prevtail->next = revlist(L);
                cur = prevtail = L;
                if(cur)
                    cur->next = nthead;
            }
            else
            {
                cur = prevtail = R;
            }
        }
        return head;
    }
    ListNode* revlist(ListNode* head)
    {
        ListNode* prev = NULL, *cur = head, *nt = NULL;
        while(cur)
        {
            nt = cur->next;
            cur->next = prev;
            prev = cur;
            cur = nt;
        }
        return prev;
    }
};