列表

详情

2074. 反转偶数长度组的节点

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

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

注意，最后一组的长度可能小于或者等于 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 ，没有发生反转。

 

提示：

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
/** * 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) { } };

java 解法, 执行用时: 35 ms, 内存消耗: 63.5 MB, 提交时间: 2023-09-07 10:33:27 

/**
 * 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) {
        List<Integer> nums = new ArrayList<>();
        ListNode p = head;
        while (p != null) {
            nums.add(p.val);
            p = p.next;
        }

        int n = nums.size();
        List<Integer> cur_nums;
        int cur_len = 1;

        ListNode dummy = new ListNode(-1);
        p = dummy;
        int i = 0;
        while (i < n) {
            cur_nums = new ArrayList<>(nums.subList(i, Math.min(i + cur_len, n)) );
            if (cur_nums.size() % 2 == 0) {
                Collections.reverse(cur_nums);
            }
            for (int x : cur_nums) {
                p.next = new ListNode(x);
                p = p.next;
            }
            i += cur_len;
            cur_len ++;
        }
        return dummy.next;
    }
}

python3 解法, 执行用时: 1992 ms, 内存消耗: 50.8 MB, 提交时间: 2023-09-07 10:30:34 

# 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]:
        i = 0
        cur, pre = head, None
        while cur:
            i += 1
            it = cur
            length = 0
            while length < i and it:
                length += 1
                it = it.next
            
            if length & 1:
                for j in range(length):
                    pre, cur = cur, cur.next
            else:
                for j in range(length - 1):
                    pre.next, cur.next.next, cur.next = cur.next, pre.next, cur.next.next
                pre, cur = cur, cur.next

        return head

golang 解法, 执行用时: 384 ms, 内存消耗: 9.4 MB, 提交时间: 2023-09-07 10:27:01 

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseEvenLengthGroups(head *ListNode) *ListNode {
	var nodes []*ListNode
	for node, size := head, 1; node != nil; node = node.Next {
		nodes = append(nodes, node)
		if len(nodes) == size || node.Next == nil { // 统计到 size 个节点，或到达链表末尾
			if n := len(nodes); n%2 == 0 { // 有偶数个节点
				for i := 0; i < n/2; i++ {
					nodes[i].Val, nodes[n-1-i].Val = nodes[n-1-i].Val, nodes[i].Val // 直接交换元素值
				}
			}
			nodes = nil
			size++
		}
	}
	return head
}

上一题

© 2024 leetcode.cn