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

题目描述

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

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

解法一：递归

使用递归的方式处理每k个一组的结点，具体处理方式如下：

  • 首先用tail记录每次翻转的尾部，就是第k+1个结点，从头结点开始，遍历链表，找到第k+1个结点，如果当前结点数不够k个，则不用反转直接返回；
  • 然后从链表头开始遍历，翻转结点并记录反转后的表头pre和表尾结点head；
  • 然后递归处理从tail开始的后面的链表结点，并将head指向递归处理后的链表；
  • 返回新的表头即为反转后的新的链表的表头结点。

代码

  1. public class Bm003 {
  2.     /**
  3.      * 递归
  4.      *
  5.      * @param head ListNode类
  6.      * @param k    int整型
  7.      * @return ListNode类
  8.      */
  9.     public static ListNode reverseKGroup(ListNode head, int k) {
  10.         // 找到每次翻转的尾部
  11.         ListNode tail = head;
  12.         // 遍历k次到尾部
  13.         for (int i = 0; i < k; i++) {
  14.             // 如果不足k到了链表尾部，直接返回，不翻转
  15.             if (tail == null) {
  16.                 return head;
  17.             }
  18.             tail = tail.next;
  19.         }
  20.         // 翻转时需要的前序和当前节点
  21.         ListNode pre = null, cur = head;
  22.         // 在到达当前段尾部节点前
  23.         while (cur != tail) {
  24.             ListNode temp = cur.next;
  25.             cur.next = pre;
  26.             pre = cur;
  27.             cur = temp;
  28.         }
  29.         // 当前尾部指向下一段要翻转的链表
  30.         head.next = reverseKGroup(tail, k);
  31.         return pre;
  32.     }
  34.     public static void main(String[] args) {
  35.         ListNode head = ListNode.testCase2();
  36.         System.out.println("翻转之前");
  37.         ListNode.print(head);
  39.         // 当k=2时
  40.         ListNode newHead = reverseKGroup(head, 2);
  41.         System.out.println("当k=2时，翻转之后");
  42.         ListNode.print(newHead);
  44.         ListNode head1 = ListNode.testCase2();
  45.         // 当k=3时
  46.         ListNode newHead2 = reverseKGroup(head1, 3);
  47.         System.out.println("当k=3时，翻转之后");
  48.         ListNode.print(newHead2);
  49.     }
  50. }

牛客网高频算法题系列-BM3-链表中的节点每k个一组翻转 - 图1
牛客网高频算法题系列-BM3-链表中的节点每k个一组翻转 - 图2
相信坚持的力量！