[LeetCode] 25、K 个一组翻转链表
程序员文章站
2022-03-18 09:33:19
...
题目描述
给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。(要求空间)
给定这个链表:1->2->3->4->5
当 k = 2 时,应当返回: 2->1->4->3->5
当 k = 3 时,应当返回: 3->2->1->4->5
解题思路
链表题大多还是用“多指针”解决,一般都不会很难,注意不要断链就行。
-
栈解法(空间复杂度,其实不符合题意):
- 用栈,我们把
k
个数压入栈中,然后弹出来的顺序就是翻转的! - 这里要注意几个问题:
- 第一,剩下的节点个数够不够
k
个(因为不够k
个不用翻转); - 第二,已经翻转的部分要与剩下链表连接起来。(不要断链)
- 第一,剩下的节点个数够不够
- 用栈,我们把
-
常规解法(推荐,我的实现):其实就是画图之后模拟,注意不要断链就行了。
-
解法见下图(推荐直接看代码,更好理解)
-
参考代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode* dummyHead = new ListNode(-1);
dummyHead->next = head;
ListNode* pPre = dummyHead;
ListNode* pEnd = dummyHead;
while(pEnd != nullptr){
for(int i = 0; i < k; i++){
if(pEnd != nullptr)
pEnd = pEnd->next;
}
if(pEnd == nullptr)
break;
ListNode* pStart = pPre->next;
ListNode* pNext = pEnd->next;
pEnd->next = nullptr; // 重要
pPre->next = listReverse(pStart);
pStart->next = pNext;
pPre = pStart;
pEnd = pStart;
}
return dummyHead->next;
}
ListNode* listReverse(ListNode* head){
ListNode* pPre = nullptr;
ListNode* pNode = head;
while(pNode != nullptr){
ListNode* pNext = pNode->next;
pNode->next = pPre;
pPre = pNode;
pNode = pNext;
}
return pPre;
}
};
上一篇: 快速掌握jmeter的基本操作和使⽤
下一篇: leetcode查询重复的电子邮箱