LeetCode25 K个一组反转链表

LeetCode25 K个一组反转链表

1. 代码实现

   class Solution {
       public ListNode reverseKGroup(ListNode head, int k) {
           if (head == null) return null;
           ListNode a, b;
           a = b = head;
           for (int i = 0; i < k; i++) {
               if (b == null) {
                   return head;
               }
               b = b.next;
           }
   
           ListNode newHead = reverse(a,b);
           a.next = reverseKGroup(b, k);
           return newHead;
       }
   
       ListNode reverse(ListNode head, ListNode b) {
           ListNode cur = head;
           ListNode pre = null;
           ListNode temp = null;
           while (cur != b) {
               temp = cur.next;
               cur.next = pre;
               pre = cur;
               cur = temp;
           }
           return pre;
       }
   }
   

2. 思路分析

   1. 分析问题： 我们如果对这个链表进行reverseKGroup(head, 2)，即以2个节点为一组进行反转；当我们完成反转后，发现该链表中剩余的未反转节点也是一条链表，而且规模比之前的链表小了，这就是子问题

   2. 对于子问题可以采用递归：我们可以在反转完一次后，将head节点移动到子链表的开头，再进行反转，一次往复，直到反转完成——剩余的子链表节点个数小于k，这也就是base case

   3. 算法流程

      1. 先反转以head开头的k个元素，再让head指向第k+1个节点

      2. 递归调用reverseKGroup(head, 2)

         [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-vWSa1GTE-1652965914056)(https://s2.loli.net/2022/05/19/FluOCqBprfg3WZ7.png)]

3. 代码分析

   1. reverse()为双指针反转链表，可看前文
   2. reverseKGroup()执行流程
      1. 执行过程即为上述递归调用
      2. 执行结果