Leetcode_hot100_25.K个一组翻转链表

题目要求

  • 给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

  • k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

  • 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

示例 1:

输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]

示例 2:

输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]

参考反转链表

反转链表【基础算法精讲 06】

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
/**
 * 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 reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0, head);
        ListNode p0 = dummy;
        ListNode cur = head;
        int len = 0;
        while (cur != null) {
            cur = cur.next;
            len++;
        }

        int m = len / k;

        // 反转前k个
        ListNode pre = null;
        ListNode nxt = null;
        for (int i = 0; i < m; i++){
            pre = null;
            cur = p0.next;
            for (int j = 0; j < k; j++) {
                nxt = cur.next;
                cur.next = pre;
                pre = cur;
                cur = nxt;
            } 

            nxt = p0.next;
            p0.next.next = cur;
            p0.next = pre;
            p0 = nxt;
        }

        return dummy.next;
    }
}
  • 时间复杂度：O(n)O(n)。
  • 空间复杂度：O(1)O(1)。