（算法）K个⼀组翻转链表————＜链表—模拟＞

1. 题⽬链接：25.K个⼀组翻转链表

2. 题⽬描述：

3. 解法（模拟）：

算法思路：

本题的⽬标⾮常清晰易懂，不涉及复杂的算法，只是实现过程中需要考虑的细节⽐较多。

我们可以把链表按K 个为⼀组进⾏分组，组内进⾏反转，并且记录反转后的头尾结点，使其可以和 前、后连接起来。思路⽐较简单，但是实现起来是⽐较复杂的。

我们可以先求出⼀共需要逆序多少组（假设逆序n 组），然后重复n 次⻓度为k 的链表的逆序即 可。 

C++算法代码： 

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution 
{
public:
    ListNode* reverseKGroup(ListNode* head, int k) 
    {
        int num=0;  //需要翻转的组数
        ListNode* temp=head; 
        while(temp)
        {
            temp=temp->next;
            num++;
        }
        num/=k;
        //头插法翻转每组链表
        ListNode* new_head=new ListNode(0);  //新的头结点
        ListNode* key=new_head;
        ListNode* cur;
        //翻转完整的组
        for(int i=0;i<num;i++)
        {
            ListNode* cur1=head; //记录每组的第一个空间
            for(int j=0;j<k;j++)
            {
                //存储下一个位置
                cur=head->next;
                //头插
                head->next=key->next;
                key->next=head;
                //更新位置
                head=cur;
            }
            key=cur1;
        }
        //加上无需翻转的部分
        while(head)
        {
            key->next=head;
            head=head->next;
            key=key->next;
        }
        cur=new_head->next;
        delete new_head;
        return cur;
    }
};

Java算法代码：

/**
 * 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)
	{
		// 1. 先求出需要逆序多少组 
		int n = 0;
		ListNode cur = head;
		while (cur != null)
		{
			cur = cur.next;
			n++;
		}
		n /= k;
		// 2. 重复 n 次：⻓度为 k 的链表的逆序 
		ListNode newHead = new ListNode(0);
		ListNode prev = newHead;
		cur = head;
		for (int i = 0; i < n; i++)
		{
			ListNode tmp = cur;
			for (int j = 0; j < k; j++)
			{
				// 头插的逻辑 
				ListNode next = cur.next;
				cur.next = prev.next;
				prev.next = cur;
				cur = next;
			}
			prev = tmp;
		}
		// 把后⾯不需要逆序的部分连接上 
		prev.next = cur;
		return newHead.next;
	}
}