每日一题：BM1 反转链表

文章目录

• • • @[toc]
    • 问题描述
    • • 数据范围
      • 示例
    • C++代码实现
    • • 使用栈实现（不符合要求，仅作为思路）
    • 解题思路 - 原地反转链表
    • • 步骤
    • C语言代码实现

以前只用过C++刷过代码题目，现在试着用C语言刷下

问题描述

给定一个单链表的头结点 pHead，反转该链表后返回新链表的表头。

数据范围

• 链表长度 $0\le n\le 1000$
• 要求：空间复杂度 $O(1)$，时间复杂度 $O(n)$

示例

1. 输入：{1,2,3}
   输出：{3,2,1}

2. 输入：{}
   输出：{}

如果链表为空，则直接返回空。

---

C++代码实现

最开始尝试用 C++ 的 栈 实现，结果想到C语言不能直接调用栈，玛德。但考虑到题目要求空间复杂度为 $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;stack<ListNode*> 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(1)$ 的要求，我们使用三个指针实现链表的 原地反转：

步骤

1. 初始化

   • prev：指向当前节点的前驱节点（初始为 NULL）。
   • cur：指向当前节点。
   • next：临时保存当前节点的后继节点。

2. 反转过程

   • 逐一将当前节点的 next 指针指向 prev。
   • 将 prev 和 cur 向后移动。

3. 结束条件

   • 当 cur 遍历到链表尾部（即 cur ->next== NULL），同时别忘了，把最后一个结点也给处理了，cur->next=pre。链表反转完成，此时 cur 即为新链表头。

---

C语言代码实现

/*** struct ListNode {*	int val;*	struct ListNode *next;* };*/
/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param head ListNode类 * @return ListNode类*/
struct ListNode* ReverseList(struct ListNode* head ) {if(head==NULL)return head;struct ListNode* cur=head;struct ListNode* pre=NULL;struct ListNode* next=cur->next;while(cur->next!=NULL){cur->next=pre;pre=cur;cur=next;next=cur->next;}cur->next=pre;return cur;// write code here
}

---

轻松拿捏。