分析

大致过程可以分解为:

  • 找到待翻转的k个节点(若剩余数量小于k的话,则不需要反转,因此直接返回待翻转部分的头结点即可)。

  • 对这k个节点反转,并返回翻转后的头结点。

    1.在翻转链表的时候,可以借助三个指针:prev、curr、next,分别代表前一个节点、当前节点和下一个节点。

    2.curr指向的下一节点保存到next指针。

    3.curr指向prev,一起前进一步。

    4.重复之前步骤,直到 k 个元素翻转完毕。

    5.当完成了局部的翻转后,prev就是最终的新的链表头,curr指向了下一个要被处理的局部,而原来的头指针head 成为了链表的尾巴。

  • 对下一轮k个节点也进行翻转操作。
  • 将上一轮翻转后的尾结点指向下一轮翻转后的头节点。

代码

class Solution {
   public ListNode reverseKGroup(ListNode head, int k) {
       //三个指针prev、curr、next,分别代表前一个节点、当前节点和下一个节点
        ListNode prev = null;
        ListNode curr = head;
        ListNode next;
        int n = k;
        //判断剩余的数量,剩余数量小于k则不需要反转
        ListNode tail = curr;
        for (int i = 0; i < k; i++) {
            if(tail==null) {
                return head;
            }
            tail = tail.next;
        }
        //局部反转(k个元素)
        while (curr != null && n-- > 0) {
            next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        //prev成为新的链表头,curr指向了下一个要被处理的局部的第一个元素,原来的头指针head成为了链表的尾巴
        ListNode newHead = prev;

        //将上一轮翻转后的尾结点指向下一轮翻转后的头节点
        head.next = reverseKGroup(curr, k);
        return newHead;
    }
    }
Last modification:April 9th, 2020 at 10:09 pm