【LeetCode】25.K 个一组翻转链表_给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。 k 是一个正整数,

一、题目

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

示例：
给你这个链表：1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5

说明：
你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

二、解决

1、迭代法

思路：

代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode preHead = dummy;
        while (preHead != null) {
            ListNode node = preHead;
            // Check whether there are k nodes to reverse, jump out when it meets Kth node for given list.
            for (int i = 0; i < k && node != null; i++) {
                node = node.next;
            }
            if (node == null) { break; }

            // Reverse lists if there exist k nodes
            preHead = reverse(preHead, k);
        }
        return dummy.next;
    }
    
    public ListNode reverse(ListNode preHead, int k){
        ListNode head = preHead.next;
        ListNode prev = null;
        ListNode curr = head;
        for (int i = 0; i < k; i++) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        preHead.next = prev;
        head.next = curr;
        return head;
    }
}
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

时间复杂度： O(n)
空间复杂度： O(1)

2、递归法

思路：图来自参考2。

代码：

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {

        ListNode tail = head;
        for (int i = 0; i < k; i++) {
            //剩余数量小于k的话，则不需要反转。
            if (tail==null) { return head; }
            tail = tail.next;
        }
        // 反转前 k 个元素
        ListNode newHead = reverse(head, tail);
        //下一轮的开始的地方就是tail
        head.next = reverseKGroup(tail, k);
        return newHead;
    }

    private ListNode reverse(ListNode head, ListNode tail) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != tail) {
            ListNode nextNode = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextNode;
        }
        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

时间复杂度： O(n)
空间复杂度： klogk

三、参考

1、图解k个一组翻转链表
2、递归java
3、Short but recursive Java code with comments
4、Non-recursive Java solution and idea
5、Java O(n) solution with super detailed explanation & illustration