leetcode 25. Reverse Nodes in k-Group | 25. K 个一组翻转链表（Java）

旧城等待， 2022-08-30 05:16 144阅读 0赞

## 题目 ##

[https://leetcode.com/problems/reverse-nodes-in-k-group/][https_leetcode.com_problems_reverse-nodes-in-k-group]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]

## 题解 ##

乍一看以为很容易：每 k 个节点翻转，若剩余不足 k 个，则不变。没有什么技巧，但是有很多要考虑的细节，折腾了一个小时…  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 1]

/** * 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) { 
            if (k == 1) return head;
            ListNode newHead = null;
            ListNode preLast = new ListNode(); // 前一翻转区间的末尾节点
            preLast.next = head;
            ListNode curLast = null; // 当前翻转区间的末尾节点
            ListNode nextFirst = head; // 下一翻转区间的起始节点
            while (nextFirst != null) { 
            	// 让nextFirst指向下一个区间
                for (int i = 0; i < k; i++) { 
                    curLast = nextFirst;
                    if (nextFirst != null) nextFirst = nextFirst.next;
                    else break;
                }
                if (curLast == null) break;
                ListNode L = preLast.next;
                ListNode M = L.next;
                ListNode R = M.next;
                preLast.next.next = nextFirst;
                // 翻转当前区间
                do { 
                    M.next = L;
                    L = M;
                    M = R;
                    if (R != null) R = R.next;
                } while (L != curLast);
                ListNode temp = preLast.next;
                preLast.next = curLast;
                preLast = temp;
                if (newHead == null) newHead = curLast;
            }
            return newHead;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

[https_leetcode.com_problems_reverse-nodes-in-k-group]: https://leetcode.com/problems/reverse-nodes-in-k-group/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]: /images/20220829/67ded98df5e348169240eeac80668c0a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 1]: /images/20220829/fd640a1254324270bb6e82b970063f21.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20220829/4d65d3eb643a4d229caf0d76bbb7a5a5.png