关于java:牛客网高频算法题系列BM3链表中的节点每k个一组翻转

29次阅读

共计 1188 个字符，预计需要花费 3 分钟才能阅读完成。

将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表如果链表中的节点数不是 k 的倍数，将最初剩下的节点放弃原样你不能更改节点中的值，只能更改节点自身。

原题目见：BM3 链表中的节点每 k 个一组翻转

应用递归的形式解决每 k 个一组的结点，具体解决形式如下：

首先用 tail 记录每次翻转的尾部，就是第 k + 1 个结点，从头结点开始，遍历链表，找到第 k + 1 个结点，如果以后结点数不够 k 个，则不必反转间接返回；

而后从链表头开始遍历，翻转结点并记录反转后的表头 pre 和表尾结点 head；

而后递归解决从 tail 开始的前面的链表结点，并将 head 指向递归解决后的链表；

返回新的表头即为反转后的新的链表的表头结点。

public class Bm003 {
    /**
     * 递归
     *
     * @param head ListNode 类
     * @param k    int 整型
     * @return ListNode 类
     */
    public static ListNode reverseKGroup(ListNode head, int k) {
        // 找到每次翻转的尾部
        ListNode tail = head;
        // 遍历 k 次到尾部
        for (int i = 0; i < k; i++) {
            // 如果有余 k 到了链表尾部，间接返回，不翻转
            if (tail == null) {return head;}
            tail = tail.next;
        }
        // 翻转时须要的前序和以后节点
        ListNode pre = null, cur = head;
        // 在达到以后段尾部节点前
        while (cur != tail) {
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        // 以后尾部指向下一段要翻转的链表
        head.next = reverseKGroup(tail, k);
        return pre;
    }

    public static void main(String[] args) {ListNode head = ListNode.testCase2();
        System.out.println("翻转之前");
        ListNode.print(head);

        // 当 k = 2 时
        ListNode newHead = reverseKGroup(head, 2);
        System.out.println("当 k = 2 时，翻转之后");
        ListNode.print(newHead);

        ListNode head1 = ListNode.testCase2();
        // 当 k = 3 时
        ListNode newHead2 = reverseKGroup(head1, 3);
        System.out.println("当 k = 3 时，翻转之后");
        ListNode.print(newHead2);
    }
}