avatar-decorate
获赞
908
粉丝
85
关注
30
看过 TA
503
贵州大学
2022
C++
IP属地:广东
打工人打工魂
私信
关注
头像
2021-07-21 08:44
已编辑
网易互娱_互娱_底层研发工程师
题解一:迭代翻转 题解思路 : 建立一个空白节点指向头节点,然后翻转[m,n]内的节点。 参数分析: p:指向m前一个节点,q指向第n个节点。p1,p2用于翻转. 图示:复杂度分析: 时间复杂度:O(N),最多遍历整个链表 空间复杂度:O(1),只使用了常数个变量实现如下: class Solution { public: /** * * @param head ListNode类 * @param m int整型 * @param n int整型 * @return ListNode类 */ ListNode* reverseBetween(ListNode* head, int m, in...
夜仙森Yuki:您的代码中存在几个问题,主要涉及到C++和链表操作的混合使用,以及一些逻辑上的小错误。首先,您使用了malloc来分配内存,这是C语言中的做法,而在C++中通常推荐使用new操作符或者智能指针(如std::unique_ptr)。其次,您在反转链表节点时的逻辑处理有误,导致可能的链表断裂或无限循环。 下面是修改后的C++代码,去除了malloc的使用,并修正了反转链表部分的逻辑: cpp #include <iostream> struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} }; class Solution { public: ListNode* reverseBetween(ListNode* head, int m, int n) { if (head == nullptr || head->next == nullptr || m == n) return head; ListNode* dummy = new ListNode(0); // 创建哑节点 dummy->next = head; ListNode* prev = dummy; ListNode* curr = head; // 将prev移动到第m-1个节点 for (int i = 1; i < m; ++i) { prev = prev->next; curr = curr->next; } ListNode* start = curr; // 第m个节点 ListNode* thenext = nullptr; // 反转第m到第n个节点 for (int i = m; i <= n; ++i) { thenext = curr->next; curr->next = prev->next; prev->next = curr; curr = thenext; } // 将start的下一个节点连接到第n+1个节点 start->next = curr; ListNode* newHead = dummy->next; delete dummy; // 释放哑节点内存 return newHead; } }; // 用于测试的代码 int main() { // 示例链表 1->2->3->4->5 ListNode* head = new ListNode(1); head->next = new ListNode(2); head->next->next = new ListNode(3); head->next->next->next = new ListNode(4); head->next->next->next->next = new ListNode(5); Solution sol; ListNode* reversedHead = sol.reverseBetween(head, 2, 4); // 打印反转后的链表 while (reversedHead != nullptr) { std::cout << reversedHead->val << " "; ListNode* temp = reversedHead; reversedHead = reversedHead->next; delete temp; // 释放链表节点内存 } return 0; } 注意: 我添加了一个哑节点(dummy node)来简化边界条件的处理。 使用new操作符创建节点,并在主函数中释放了所有动态分配的内存。 修正了反转链表的逻辑,确保在反转后正确地连接前后的链表部分。 添加了测试代码来验证函数的功能。
牛客网编程题题解
0 点赞 评论 收藏
分享

创作者周榜

更多
关注他的用户也关注了:
牛客网
牛客网在线编程
牛客网题解
牛客企业服务