这题现在已经是面试高频题了,字节尤其爱考。
递归法,每k个节点一组进行反转,下一组链表接到当前组的末尾。
最后递归那里不太好理解,画个图大家伙看看
class Solution {
public:
ListNode* reverse(ListNode* head, ListNode* tail) //反转链表模板,面试高频题
{
ListNode *pre = head, *cur = head->next;
while (cur != tail)
{
ListNode* ne = cur->next;
cur->next = pre;
pre = cur, cur = ne;
}
head->next = nullptr;
return pre;
}
ListNode* reverseKGroup(ListNode* head, int k) {
if (head == nullptr || head->next == nullptr) return head;
ListNode* tail = head;
for (int i = 0; i < k; ++ i) //遍历k个节点
{
if (tail == nullptr) return head; //不足k个节点则不反转,直接返回
//注意,如果这里面试官要求最后不足k个也要翻转,就得改成下面一行
//if (tail == nullptr) return reverse(head, tail);
tail = tail->next;
}
ListNode* newhead = reverse(head, tail); //反转长度为k的链表
head->next = reverseKGroup(tail, k); //递归将下一段反转链表接到当前段的尾部
return newhead;
}
};