文章目录
1. 题目
2. 解题
1. 题目
给你一个链表的头节点 head 。
链表中的节点 按顺序 划分成若干 非空 组，这些非空组的长度构成一个自然数序列（1, 2, 3, 4, …）。一个组的 长度 就是组中分配到的节点数目。换句话说：
节点 1 分配给第一组
节点 2 和 3 分配给第二组
节点 4、5 和 6 分配给第三组，以此类推
注意，最后一组的长度可能小于或者等于 1 + 倒数第二组的长度 。
反转 每个 偶数 长度组中的节点，并返回修改后链表的头节点 head 。
示例 1：
输入：head = [2,1] 输出：[2,1] 解释： - 第一组长度为 1 ，没有发生反转。 - 最后一组长度为 1 ，没有发生反转。 示例 4： 输入：head = [8] 输出：[8] 解释：只有一个长度为 1 的组，没有发生反转。 提示： 链表中节点数目范围是 [1, 10^5] 0 <= Node.val <= 10^5
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; } };
876 ms 321.8 MB C++
