【剑斩OFFER】算法的暴力美学——K 个一组翻转链表

一、题目描述

二、算法原理

思路：

1）计算要逆序的链表对

2）创建一个哨兵位，分别把要逆序的结点头插到这个哨兵位上

插入完一对逆序对之后：

再头插到 prev 结点的后面：

3）把除链表逆序对的结点插入到这个哨兵位的最后结点上

三、代码实现

/** * 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 length = 0; ListNode* node = head; while(node) { length++; node = node->next; } //计算要逆序链表中的对数 int size = length / k; ListNode* head2 = new ListNode(0);//哨兵位 ListNode* prev = head2;//头插的位置 ListNode* cur = head; int num = 0;//记录插入的个数 while(size) { prev->next = cur; ListNode* next_prev = cur;//下一个头插的结点 ListNode* tmp = cur->next; cur->next = nullptr; num++; cur = tmp; while(num != k) { tmp = prev->next; prev->next = cur; num++; ListNode* next_cur = cur->next; cur->next = tmp; cur = next_cur; } prev = next_prev; num = 0; size--;//每逆行一对就减一 } if(cur) prev->next = cur;//连接逆转之后剩余的结点 ListNode* result = head2->next; delete head2; return result; } };