算法通关村|黄金挑战|K个一组进行反转

K个一组进行反转

1.头插法

public ListNode reverseKGroup(ListNode head, int k) {
	ListNode dummyNode = new ListNode(0);
    dummyNode.next = head;
    ListNode cur = head;
    // 计算链表长度
    int len = 0;
    while (cur != null) {
        len++;
        cur = cur.next;
    }
    // 计算有几组
    int n = len / k;
    ListNode pre = dummyNode;
    cur = head;
    // 一共进行n次反转
    for (int i = 0; i < n; i++) {
        // 每次反转操作将cur移动k-1次
        for (int j = 0; j < k - 1; j++) {
            ListNode next = cur.next;
            cur.next = cur.next.next;
            next.next = pre.next;
            pre.next = next;
        }
        pre = cur;
        cur = cur.next;
    }
    return dummyNode.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

2.穿针引线法

public ListNode reverseKGroup(ListNode head, int k) {
	ListNode dummyNode = new ListNode(0);
    dummyNode.next = head;
    ListNode pre = dummyNode;
    ListNode end = dummyNode;
    while (end.next != null) {
        // 找到每次处理的一段区间的末尾处，移动k次
    	for (int i = 0; i < k && end != null; i++) {
            end = end.next;
        }
        if (end == null) {
            break;
        }
        ListNode start = pre.next;
        ListNode next = end.next;
        // 与后边的链表断开
        end.next = null;
        // 调用反转方法，将断开的这一段链表反转，并且和前边的链表相连接
        pre.next = reverse(start);
        // 现在start是这段链表的末尾处，将其与后边的链表相连接
        start.next = next;
        // 把pre和end指针移动到下一个区间的前一个位置
        pre = start;
        end = pre;
    }
    return dummyNode.next;
}

// 反转实现
private ListNode reverse(ListNode head) {
	ListNode pre = null;
	ListNode curr = head;
	while (curr != null) {
        ListNode next = curr.next;
        curr.next = pre;
        pre = curr;
        curr = next;
    }
	return pre;
}
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

如果对您有帮助，请点赞关注支持我，谢谢！❤
如有错误或者不足之处，敬请指正！❤