剑指 Offer 24.反转链表
大家好,我是程序员吴师兄,欢迎来到 图解剑指 Offer 结构化专栏,在这个专栏里我将和大家一起学习如何用结构化的思维来思考、解题、写代码,希望能帮助你即使在面试的时候紧张也能做对。
AlgoMooc 算法慕课网,致力于帮助每个程序员通过算法面试!
今天分享的题目来源于 LeetCode 上的剑指 Offer 系列 面试题 24.反转链表。
题目汇总链接:https://www.algomooc.com/jianzhioffer
一、题目描述
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题?
二、题目解析
我们依旧用 四步分析法 进行结构化的分析。
- 模拟:模拟题目的运行。
- 规律:尝试总结出题目的一般规律和特点。
- 匹配:找到符合这些特点的数据结构与算法。
- 边界:考虑特殊情况。
1、模拟
要想从输入链表:
输入: 1->2->3->4->5->NULL
变成输出链表:
输出: 5->4->3->2->1->NULL
意味着每个节点的下一节点(next)变成了它的前节点(pre)。
那思路就是去遍历整个链表,然后执行把每个节点的下一节点(next)变成它的前节点(pre)这个操作。
2、规律
设置三个节点 pre
、cur
、next
,其中 pre
为原链表之前的空节点,cur
为原链表的头节点,next
为 cur
的下一节点:
- (1)每次查看
cur
节点是否为NULL
,如果是,则结束循环,获得结果 - (2)如果
cur
节点不是为NULL
,则先设置临时变量next
为cur
的下一个节点 - (3)让
cur
的下一个节点变成指向pre
,而后pre
移动cur
,cur
移动到next
- (4)重复(1)(2)(3)
3、匹配
无
4、边界
无
三、动画描述
隐藏内容
四、图片描述
五、参考代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
class Solution {
public ListNode reverseList(ListNode head) {
//设置节点 cur 和节点 pre,其中 cur 为原链表的头节点,pre 为原链表之前的空节点
ListNode cur = head, pre = null;
// 不断的遍历链表,直到遍历到链表的尾部
while (cur != null) {
// 获取的当前节点 cur 的下一个节点
ListNode next = cur.next;
// 修改当前节点的下一个节点为 pre
cur.next = pre;
// pre 向前移动,变成了 cur
pre = cur;
// cur 向前移动,变成了 next
cur = next;
}
// 返回 pre
return pre;
}
}
六、复杂度分析
时间复杂度
时间复杂度为 O(N)。
空间复杂度
空间复杂度为 O(1)。
七、相关标签
- 链表