【LeetCode】第25题：K 个一组翻转链表（字节跳动面试题）

本是古典何须时尚 2021-12-05 15:19 218阅读 0赞

LeetCode 链接：[https://leetcode-cn.com/problems/reverse-nodes-in-k-group/][https_leetcode-cn.com_problems_reverse-nodes-in-k-group]

**题目：给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。**

> 示例 :
> 
> 给定这个链表：1->2->3->4->5
> 
> 当 k = 2 时，应当返回: 2->1->4->3->5
> 
> 当 k = 3 时，应当返回: 3->2->1->4->5
> 
> 说明 :
> 
> 你的算法只能使用常数的额外空间。  
> 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

思路：其实翻转链表的题目大家都做过，一个 while 循环就解决了。那么每 k 个节点一组进行翻转，其实也类似。只需要递归的每次把 k 个节点为一组进行翻转就行。这个时候需要注意的是几个指针的指向情况： 每次翻转的头结点（1、k + 1...）、翻转后两段之间连接的结点（比如1~k 和 k + 1 ~ 2k 之间连接的两个结点就是 1 和 2k， 即 1 的 next 指针指向的是 2k）等。

*  ### 代码实现 ###

public class ReverseKGroup_25 {
    
        public class ListNode{
            int val;
            ListNode next;
    
            public ListNode(int val){
                this.val = val;
            }
        }
    
        public ListNode reverseKGroup(ListNode head, int k){
            // 判断链表中元素的个数
            int count = 0;
            ListNode current = head;
            while(current != null){
                count++;
                current = current.next;
                // k - 1是因为next到了k个
                if(count == k - 1){
                    break;
                }
            }
            // 如果当前temp的下一个节点为空，说明个数不够k，则直接返回
            if(current == null){
                return head;
            }
    
            int num = k;       // 保存翻转的次数
            ListNode tempHead = head;  // 保存递归后连接的头结点
            // 翻转链表
            ListNode pre = null;
            while(num > 0){
                // 在head的next指针断开前，先保存它的next指针指向的对象
                ListNode next = head.next;
                head.next = pre;
                pre = head;
                head = next;
                num--;
            }
            // current.next为下一次翻转的头结点
            current = current.next;
            tempHead.next = reverseKGroup(current, k);
            return pre;
        }
    }

[https_leetcode-cn.com_problems_reverse-nodes-in-k-group]: https://leetcode-cn.com/problems/reverse-nodes-in-k-group/