K个节点翻转链表
概述
起因:leetcode题目 25. K 个一组翻转链表
问题描述
给你链表的头节点 head ,每 k 个节点一组进行翻转,请你返回修改后的链表。
k 是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。
示例一:
输入:head = [1,2,3,4,5], k = 2
输出:[2,1,4,3,5]
示例 2:
输入:head = [1,2,3,4,5], k = 3
输出:[3,2,1,4,5]
解决方法
我们需要构建一个函数,它会对链表进行K个节点翻转。而不断使用这个函数,就可以对每K个节点进行翻转。
点击查看代码
struct Res{
ListNode *head;
bool flag;
ListNode *tail;
};
Res reverse(ListNode* head,int k){
ListNode newHead;
ListNode *subHead,*subTail,*cur,*temp;
//subHead 记录反转过程的头节点
//subTail 记录反转过程的尾节点
//cur 要反转的节点
//temp 用于反转的中间变量
int cnt = 0; //记录长度
if(head){
subHead = head;
subTail = head;
cur = head->next;
cnt++;
}
while(cur && cnt<k){
temp = cur;
cur = cur->next;
subTail->next = temp->next;
temp->next = subHead;
subHead = temp;
cnt++;
}
bool flag = true;
if(cnt<k) flag = false;
return {subHead,flag,subTail};
}
函数逻辑
-
一开始翻转链表的
head
和tail
都是正常链表的头节点,cur
则是要进行翻转的节点- 我们把
cur
作为新的head
,即旧的head
会成为cur
的下一个节点。 cnt
进行自增加一
- 我们把
-
重复这个过程,直到
cur
为空。 -
然后判断
cnt
与K
的关系:cnt
<K
的话,则未能反转K
个节点。flag
为 False。
注意:这个过程中
tail
不需要变化,因为一开始的正常链表头节点就是翻转后的尾节点。
其中,函数返回翻转后的头节点和尾节点。特别地,flag是判断是否翻转了K个数。
实现不满足K个节点则不翻转
当不满足K个节点时,函数返回的 res
中的flag
属性会为False。
这时对这个翻转后的链表再次进行翻转的话,就可以实现不翻转。
主函数实现
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode *newHead,*subTail;
//首先进行一次翻转,并初始newHead和subTail
auto res = reverse(head,k);
newHead = res.head;
subTail = res.tail;
//如果第一次翻转就不满足K个节点,再次进行翻转,并返回新的newHead
if(res.flag == false){
res = reverse(newHead,k);
newHead = res.head;
subTail = res.tail;
return newHead;
}
//对每K个节点进行翻转
while(1){
auto res = reverse(subTail->next,k);
//不满足K个节点,再次翻转,并直接返回结果。
if(res.flag == false){
res = reverse(res.head,k);
return newHead;
}
// 对subTail进行更新:链接翻转后的子链表,并把subTail更新为子链表的tail。
subTail->next = res.head;
subTail = res.tail;
cout<<subTail->val<<endl;
}
return newHead;
}