【算法】【线性表】【链表】K 个一组翻转链表

1  题目

给你链表的头节点 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]

提示：

• 链表中的节点数目为 n
• 1 <= k <= n <= 5000
• 0 <= Node.val <= 1000

进阶：你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗？

2  解答

嘿嘿，咱解决了：

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // 参数边界校验
        if (head == null || head.next == null || k <= 1) {
            return head;
        }
        // 加一个头节点
        ListNode preNode = new ListNode(0);
        preNode.next = head;

        // node用于遍历 markNode永远指向一组node的前一个node
        ListNode node = preNode, markNode = preNode, startNode = null;
        // count计数器
        int count = 0;
        while (node != null) {
            if (count == 1) {
                startNode = node;
            }
            // 到达一组
            if (count == k) {
                // 反转这组链表 头插法反转
                System.out.println(String.format("%s-%s-%s", markNode.val, startNode.val, k));
                reverseGroup(markNode, startNode, k);
                // 继续下一组  这两行细细品  我原来写的是 markNode = node 因为我理解的是node就是这组的最后一个，也是下一组的前一个节点  但是不然没因为反转以后它已经往前移动了，所以应该是startNode才是下一组的前一个节点
                markNode = startNode;
                // node 也从 startNode开始 表示下一组的前一个节点
                node = startNode;
                startNode = null;
                count = 0;
                continue;
            }
            count++;
            node = node.next;
        }

        return preNode.next;
    }

    private void reverseGroup(ListNode preNode, ListNode startNode, int total) {
        int count = 1;
        while (count < total) {
            // 这里细细品 头插法往前插入
            ListNode nextNode = startNode.next;
            startNode.next = nextNode.next;
            nextNode.next = preNode.next;
            preNode.next = nextNode;
            count++;
        }
    }
}

加油。