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

题目形容

将给出的链表中的节点每 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);    }}
$1.01^{365} ≈ 37.7834343329$
$0.99^{365} ≈ 0.02551796445$
置信保持的力量！