🌕 25. K 个一组翻转链表

难度: 🌕

问题描述

---

解法

/**
 * Definition for singly-linked list.
 * 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; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // 思路：
        // 每找到 k 个节点，将其和后面的节点拆分，这 k 个节点单独翻转，然后和前后的本来节点串起来
        ListNode res = null; // 保存第一个翻转后的头结点，作为 res
        ListNode pre = null;
        ListNode l = head;
        ListNode r = head;
        while(r != null) {
            for(int i = 0; i < k - 1; i ++) {
                r = r.next;
                if(r == null) {
                    if(res == null) {
                        // 说明长度一次也没有反转过
                        return head;
                    } else {
                        return res;
                    }
                }
            }
            // 将 r 和后面的节点拆分
            ListNode next = r.next;
            r.next = null;
            // 如果不是第一次拆分，那么还需要将 l 和后面的节点拆分
            if(pre != null) {
                pre.next = null;
            }
            ListNode tt = l; // 反转后的尾节点为反转前的头结点，头结点目前已知
            ListNode hh = reverse(l); // 反转部分的尾节点
            // 进行拼接
            if(pre != null) {
                pre.next = hh;
            }
            tt.next = next;
            // 修改变量对应的节点
            if(res == null) {
                res = hh;
            }
            pre = tt;
            l = next;
            r = l;
        }
        return res;
    }

    private ListNode reverse(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while(cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

---

输出