25. K 个一组翻转链表

刷题 leetcode

题目：给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。算法空间复杂度：O(1)
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

难度：困难

示例1：

输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]

示例2：

输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]

提示：
链表中的节点数目为 n
1 <= k <= n <= 5000
0 <= Node.val <= 1000

链接：https://leetcode.cn/problems/reverse-nodes-in-k-group

class Solution {
    //单链表
    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) {this.val = val;}
        ListNode(int val, ListNode next) {this.val = val;this.next = next;}
    }
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dump = new ListNode(0);
        //将伪节点与链表头节点相连  dump->1->2->3->4
        dump.next = head;
        //要反转的链表的头尾节点
        ListNode prev = dump;//pre指向每次要翻转的链表头节点的上一个节点
        ListNode end = dump;//end指向每次要翻转的链表尾节点
        while(end.next != null){
            //循环k次，将end向后移动k个节点，找到需要翻转的链表的结尾
            for (int i=0; i<k && end!=null; i++) {
                end = end.next;
            }
            if (end==null) break;
            ListNode thisHead = prev.next;//记下要翻转链表的头节点
            ListNode nextHead = end.next;//记下链表尾节点的next，方便后面链接链表
            end.next = null;//断开链表
            prev.next =  reverse(thisHead);//翻转，然后prev.next指向头节点
            thisHead.next = nextHead;//翻转后头节点变为尾节点，通过.next把断开的链表重新链接
            prev = thisHead;//prev和end设置为下次要翻转的链表头节点的上一个节点，类似dump
            end = prev;
        }
        return dump.next;
    }
    //迭代法：一个一个反转
    public ListNode reverse(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode tmp = curr.next;   //记录当前节点的下一个节点
            curr.next = prev;           //反转
            prev = curr;                //prev和curr节点都前移一位
            curr = tmp;
        }
        return prev;    //此时prev移动到了原链表的尾部，即反转后链表的首部，所以返回
    }
}