题解 | #链表中的节点每k个一组翻转#
链表中的节点每k个一组翻转
https://www.nowcoder.com/practice/b49c3dc907814e9bbfa8437c251b028e
新建一个链表头newhead，同时记录它的尾节点newtail。
遍历原链表，取每k个作为一段，然后把这样的一段段链表插入到newtail后面，用头插法插入即可得到反转链表的效果。
最后一段不足k个节点的链表，则采用尾插法 插入，无需反转。
最后返回newhead->next。
时间复杂度O(n)
空间复杂度O(1)
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
class Solution {
public:
/**
*
* @param head ListNode类
* @param k int整型
* @return ListNode类
*/
ListNode* reverseKGroup(ListNode* head, int k) {
// write code here
ListNode *thead = head, *tail = head;
ListNode *newhead = new ListNode(-1);
// newhead->next = nullptr;
ListNode *newtail = newhead;
while(tail){
for(int i=1; i<k&&tail!=nullptr; ++i){
tail = tail->next;
}
if(tail==nullptr){
//不足k个节点
// 不改变顺序插入到最后
while(thead){
newtail->next = thead;
newtail = thead;
thead=thead->next;
}
}else{
ListNode *q = thead;//保存新链表最后一个节点
while(thead!=tail){
ListNode *p = thead->next;
thead->next = newtail->next;
newtail->next = thead;
thead = p;
}
thead = tail->next;
tail->next = newtail->next;
newtail->next = tail;
tail = thead;
newtail = q;
}
}
return newhead->next;
}
};
快手成长空间 249人发布
查看14道真题和解析