题目描述
给你一个链表的头节点 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 ，没有发生反转。
提示：
- 链表中节点数目范围是
[1, 105]
0 <= Node.val <= 105
解法
方法一
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39 | # Definition for singly-linked list.
# 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]:
def reverse(head, l):
prev, cur, tail = None, head, head
i = 0
while cur and i < l:
t = cur.next
cur.next = prev
prev = cur
cur = t
i += 1
tail.next = cur
return prev
n = 0
t = head
while t:
t = t.next
n += 1
dummy = ListNode(0, head)
prev = dummy
l = 1
while (1 + l) * l // 2 <= n and prev:
if l % 2 == 0:
prev.next = reverse(prev.next, l)
i = 0
while i < l and prev:
prev = prev.next
i += 1
l += 1
left = n - l * (l - 1) // 2
if left > 0 and left % 2 == 0:
prev.next = reverse(prev.next, left)
return dummy.next
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52 | /**
* Definition for singly-linked list.
* public 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) {
int n = 0;
for (ListNode t = head; t != null; t = t.next) {
++n;
}
ListNode dummy = new ListNode(0, head);
ListNode prev = dummy;
int l = 1;
for (; (1 + l) * l / 2 <= n && prev != null; ++l) {
if (l % 2 == 0) {
ListNode node = prev.next;
prev.next = reverse(node, l);
}
for (int i = 0; i < l && prev != null; ++i) {
prev = prev.next;
}
}
int left = n - l * (l - 1) / 2;
if (left > 0 && left % 2 == 0) {
ListNode node = prev.next;
prev.next = reverse(node, left);
}
return dummy.next;
}
private ListNode reverse(ListNode head, int l) {
ListNode prev = null;
ListNode cur = head;
ListNode tail = cur;
int i = 0;
while (cur != null && i < l) {
ListNode t = cur.next;
cur.next = prev;
prev = cur;
cur = t;
++i;
}
tail.next = cur;
return prev;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38 | /**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function reverseEvenLengthGroups(head: ListNode | null): ListNode | null {
let nums = [];
let cur = head;
while (cur) {
nums.push(cur.val);
cur = cur.next;
}
const n = nums.length;
for (let i = 0, k = 1; i < n; i += k, k++) {
// 最后一组， 可能出现不足
k = Math.min(n - i, k);
if (!(k & 1)) {
let tmp = nums.splice(i, k);
tmp.reverse();
nums.splice(i, 0, ...tmp);
}
}
cur = head;
for (let num of nums) {
cur.val = num;
cur = cur.next;
}
return head;
}
|