模拟题 01K 个一组翻转链表

1. 题目描述

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

示例：

给你这个链表：1->2->3->4->5

当 k = 2 时，应当返回: 2->1->4->3->5

当 k = 3 时，应当返回: 3->2->1->4->5

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-nodes-in-k-group
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2 思路

• 把链表分为： 已经翻转部分+待翻转部分+未翻转部分
  • 未翻转部分 长度小于k 不用进行翻转

3 首先实现 单向链表的反转

• 思路 每次取一个节点 把之前已经取的放入next。直到为null

class ListNode {
     int val;
     ListNode next;
      ListNode(int x) { val = x; }
}
    public static ListNode  reverse2(ListNode head){
            ListNode t;
        ListNode pre = null; // 之前已经取的
        head = head.next;
        while (head != null) {
             t = head.next;
            head.next = pre;
            pre = head;
            head = t;
        }
        return pre;
    }

4 代码

    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode newHead = new ListNode(0);
        ListNode pre = newHead; //  待反转的前驱
        int i;
        newHead.next = head;
        ListNode end = newHead; //  待反转的最后一个节点
        do {
            i = 1;
            while (i <= k && end.next !=  null) {
                end = end.next;
                i ++;
            }
            i -- ;
            if(i == k) {
                ListNode start = pre.next;
                ListNode reverse = reverse(pre, end, k);
                pre.next = reverse;
                pre = start;
                end = start;
                // 不足k个
            } else {
                break;
            }


        } while ( end != null);
        return newHead.next;
    }
    
    public ListNode   reverse(ListNode pre, ListNode end, int k) {
        ListNode start = pre.next;

        ListNode t, ipre = end.next;
        while (k > 0) {
            t = start.next;
            start.next = ipre;
            ipre = start;
            start = t;
            k--;
        }
//      pre.next = start;
        return ipre;
    }

5 注意点

• 题目虽然不难， 但是出错了好多次， java 引用跟c区别，各种next 头晕目眩， 各种引用的变化