字节：从尾部K个节点反转链表

题目

一个链表0,1,2,3,4,5,6,7，从链表尾部 K个节点翻转，求翻转后的链表。
比如：[0,1,2,3,4,5,6,7] k=3 翻转后 [0,1,4,3,2,7,6,5]。
空间复杂度O(1)。

解法

/**
  * 链表 14,13,12,11,10,9,8,7,6,5,4,3,2,1
  * 从尾部节点1开始倒着K个一组翻转
  * 结果 14,13, 10,11,12, 7,8,9, 4,5,6, 1,2,3  请写出Java解法 要求O（1）
  * @param head
  * @param k
  * @return
  */
 public static ListNode reverseKGroupFromTail(ListNode head, int k) {
   
     //                      初始化链表 =>14，13，12，11，10，9，8，7，6，5，4，3，2，1
     //第一步 整体反转  参考 力扣 反转链表1 =>1，2，3，4，5，6，7，8，9，10，11，12，13，14
     //第二步 部分反转  参考 力扣 反转链表2 =>3，2，1，6，5，4，9，8，7，12，11，10，13，14
     //第三步 整体反转  参考 力扣 反转链表1 =>14，13 10，11，12，7，8，9，4，5，6，1，2，3
     int[] count = new int[1];
     ListNode newHead = reverseList(head,count);

     int len = count[0];
     int groups = len / 4;
     int left = 1;
     int right = k;
     //中间处理
     ListNode processingHeadLs = newHead;
     for (int i = 0; i <= groups; i++) {
   
         processingHeadLs = reverseBetween(processingHeadLs,left,right);
         left = left + k;
         right = right + k;
     }
     ListNode finalHead = reverseList(processingHeadLs);
     return finalHead;
 }

/**
 * https://leetcode.cn/problems/reverse-linked-list-ii/
 * 反转指定区间的链表
 * @param head 链表头节点
 * @param left 指定区间的起始位置
 * @param right 指定区间的结束位置
 * @return 反转区间后的链表头节点
 */
public static ListNode reverseBetween(ListNode head, int left, int right) {
   
    // 因为头节点有可能发生变化，使用虚拟头节点可以避免复杂的分类讨论
    ListNode dummyNode = new ListNode(-1);
    dummyNode.next = head;

    //pre = dummyNode 便于操作pre
    ListNode pre = dummyNode;

    // 第 1 步：从虚拟头节点走 left - 1 步，来到 left 节点的前一个节点
    // 建议写在 for 循环里，语义清晰
    for (int i = 0; i < left - 1; i++) {
   
        pre = pre.next;
    }

    // 第 2 步：从 pre 再走 right - left + 1 步，来到 right 节点
    ListNode rightNode = pre;
    for (int i = 0; i < right - left + 1; i++) {
   
        rightNode = rightNode.next;
    }

    // 第 3 步：切断出一个子链表（截取链表）
    ListNode leftNode = pre.next;
    ListNode curr = rightNode.next;

    // 注意：切断链接
    pre.next = null;
    rightNode.next = null;

    // 第 4 步：同第 206 题，反转链表的子区间
    reverseList(leftNode);

    // 第 5 步：接回到原来的链表中
    pre.next = rightNode;
    leftNode.next = curr;
    return dummyNode.next;
}

/**
 * 反转链表
 * @param head 链表头节点
 * @return prev 反转后的链表头节点
 */
private static ListNode reverseList(ListNode head) {
   
    ListNode prev = null;
    ListNode current = head;

    while (current !=null) {
   
        ListNode nextTemp = current.next;
        current.next = prev;
        prev = current;
        current = nextTemp;
    }

    return prev;
}


/**
 * 反转链表
 * @param head 链表头节点
 * @param count 用于记录链表节点数的数组
 * @return prev 反转后的链表头节点
 */
private static ListNode reverseList(ListNode head,int[] count) {
   
    ListNode prev = null;
    ListNode current = head;

    while (current !=null) {
   
        ListNode nextTemp = current.next;
        current.next = prev;
        prev = current;
        current = nextTemp;
        count[0]++;
    }

    return prev;
}

验证

System.out.println("开始");
ListNode newNode2 = ListNode.getListNode(14,13,12,11,10,9,8,7,6,5,4,3,2,1);
newNode2.toString();
ListNode newNode_k_3_tail = reverseKGroupFromTail(newNode2,3);
newNode_k_3_tail.toString();
System.out.println("结束");