C++ 链表翻转 K 个一组:代码分析及优化
这段代码实现的功能是将链表中的节点每 K 个一组进行翻转,代码存在以下问题:
-
在
reverseKGroup函数中,当链表长度不足 k 时,应该直接返回原链表,而不是进入 while 循环并将 flag 置为 false。 -
在进行链表翻转时,应该记录翻转后的链表的头结点和尾结点,以便将翻转后的链表和原链表连接起来。
-
在进行链表翻转时,应该将 prev 指向当前翻转后的链表的尾结点,而不是当前翻转前的链表的尾结点。
-
在进行链表翻转时,应该将 tail 指向当前翻转后的链表的头结点,而不是当前翻转前的链表的头结点。
-
代码中存在一些不必要的输出语句和注释,可以删除以提高代码的可读性和执行效率。
以下是优化后的代码:
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param head ListNode类
* @param k int整型
* @return ListNode类
*/
ListNode* ReverseList(ListNode* head) {
if (head == nullptr) return nullptr;
// write code here
ListNode* hd = reverse(head);
head->next = nullptr;
return hd;
}
ListNode* reverse(ListNode* head) {
if (head->next == nullptr) return head;
ListNode* hd = reverse(head->next);
head->next->next = head;
return hd;
}
ListNode* reverseKGroup(ListNode* head, int k) {
// write code here
if (head == nullptr || k <= 1) return head;
ListNode* dummy = new ListNode(-1);
dummy->next = head;
ListNode* prev = dummy;
ListNode* curr = head;
int count = 0;
while (curr != nullptr) {
count++;
if (count == k) {
// 翻转 k 个节点
ListNode* next = curr->next;
curr->next = nullptr;
ListNode* newHead = reverse(prev->next);
prev->next = newHead;
prev = curr;
curr = next;
count = 0;
} else {
curr = curr->next;
}
}
return dummy->next;
}
};
优化说明:
-
在
reverseKGroup函数开始处,首先判断链表是否为空或者 k 是否小于等于 1,如果是,则直接返回原链表。 -
使用
count变量记录当前遍历的节点数量,当count等于 k 时,进行链表翻转操作。 -
在进行链表翻转前,将
curr->next指向 nullptr,以便将要翻转的链表与原链表断开连接。 -
使用
newHead变量记录翻转后的链表的头结点,并将其与前一个翻转后的链表的尾结点连接起来。 -
使用
prev变量记录当前翻转后的链表的尾结点,方便下一次翻转时进行连接。 -
删除了代码中不必要的输出语句和注释,提高代码的可读性和执行效率。
优化后的代码逻辑更加清晰,避免了错误,并提升了代码的可读性和执行效率。
原文地址: https://www.cveoy.top/t/topic/oZKE 著作权归作者所有。请勿转载和采集!