粉末涂料做网站有用吗,卖代码建设网站,深圳国际红树林中心,化工建设信息网站文章目录 [toc]问题描述数据范围示例 C代码实现使用栈实现#xff08;不符合要求#xff0c;仅作为思路#xff09; 解题思路 - 原地反转链表步骤 C语言代码实现 以前只用过C刷过代码题目#xff0c;现在试着用C语言刷下
问题描述
给定一个单链表的头结点 pHead#xff… 文章目录 [toc]问题描述数据范围示例 C代码实现使用栈实现不符合要求仅作为思路 解题思路 - 原地反转链表步骤 C语言代码实现
以前只用过C刷过代码题目现在试着用C语言刷下
问题描述
给定一个单链表的头结点 pHead反转该链表后返回新链表的表头。
数据范围
链表长度 0 ≤ n ≤ 1000 0 \leq n \leq 1000 0≤n≤1000要求空间复杂度 O ( 1 ) O(1) O(1)时间复杂度 O ( n ) O(n) O(n)
示例 输入{1,2,3} 输出{3,2,1} 输入{} 输出{}
如果链表为空则直接返回空。 C代码实现
最开始尝试用 C 的 栈 实现结果想到C语言不能直接调用栈玛德。但考虑到题目要求空间复杂度为 O ( 1 ) O(1) O(1)栈的实现并不符合要求。
使用栈实现不符合要求仅作为思路
#include stack
#include iostream
using namespace std;// 定义链表节点
struct ListNode {int val;struct ListNode* next;ListNode(int x) : val(x), next(nullptr) {}
};// 使用栈实现链表反转
struct ListNode* ReverseList(struct ListNode* head) {if (head nullptr) // 空链表直接返回return head;stackListNode* st; // 定义一个栈ListNode* cur head;// 将所有节点压入栈while (cur ! nullptr) {st.push(cur);cur cur-next;}// 弹出栈顶元素作为新链表头ListNode* newHead st.top();st.pop();cur newHead;// 重新连接链表while (!st.empty()) {cur-next st.top();st.pop();cur cur-next;}cur-next nullptr; // 终止链表return newHead;
}此代码能实现反转但使用了辅助栈空间复杂度为 O ( n ) O(n) O(n)不符合题目要求。 解题思路 - 原地反转链表
为了满足空间复杂度 O ( 1 ) O(1) O(1) 的要求我们使用三个指针实现链表的 原地反转
步骤 初始化 prev指向当前节点的前驱节点初始为 NULL。cur指向当前节点。next临时保存当前节点的后继节点。 反转过程 逐一将当前节点的 next 指针指向 prev。将 prev 和 cur 向后移动。 结束条件 当 cur 遍历到链表尾部即 cur -next NULL同时别忘了把最后一个结点也给处理了cur-nextpre。链表反转完成此时 cur 即为新链表头。 C语言代码实现
/*** struct ListNode {* int val;* struct ListNode *next;* };*/
/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param head ListNode类 * return ListNode类*/
struct ListNode* ReverseList(struct ListNode* head ) {if(headNULL)return head;struct ListNode* curhead;struct ListNode* preNULL;struct ListNode* nextcur-next;while(cur-next!NULL){cur-nextpre;precur;curnext;nextcur-next;}cur-nextpre;return cur;// write code here
}轻松拿捏。
