25. Reverse Nodes in k-Group
问题描述
Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
Example:
Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5
Note:
- Only constant extra memory is allowed.
- You may not alter the values in the list's nodes, only nodes itself may be changed.
给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。
k 是一个正整数,它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。
题解
题目要求每k个节点一组进行翻转,返回反转后的链表。可以将算法分为两部分:分组+链表翻转;还要注意的是,如果剩余节点数目不够k个,不进行翻转,直接链接到上一组的链表上。
步骤:
- 记录链表长度;
- 循环,条件是剩余链表长度不小于k
- 一边计数一边翻转:
- 使用指针pre表示上一次翻转结果的链表尾,如果还没有进行翻转,设置为新声明的dummy节点;
- 指针cur表示需要翻转的节点;初始设置为pre指针的下一个节点;
- 进行翻转:
- 声明temp指针:记录cur的下一个节点
- 进行单节点的翻转;
- pre指针的下一个节点始终表示当前组翻转的头结点,所以每次反转后都要更新pre的next指针;
- 更新pre指针为cur;(cur指针指向当前组的最后一个节点)
- 更新链表长度k;
代码:
/**
* 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) {
ListNode *first = new ListNode(-1), *pre = first, *cur = first;
first->next = head;
int len = 0;
// 记录链表长度
while (cur = cur->next) ++len;
// 训练分组反转链表
while (len >= k){
//记录需要翻转链表的起始节点
cur = pre->next;
//依次翻转,对组内的k个节点翻转
for (int i=1; i< k; ++i){
ListNode *temp = cur->next;
cur->next = temp->next;
temp->next = pre->next;
pre->next = temp;
}
pre = cur;
len -= k;
}
return first->next;
}
};
没有想到这里的翻转方式;想到的是先找到k个节点的子链表;然后翻转,最后更新链接指针;这种方法应该也可以,过两天回顾时再看看。
Reference
https://www.cnblogs.com/grandyang/p/4441324.html
欢迎关注公众号,一起学习
网友评论