提前祝大家春节快乐~
题目
反转一个单链表。
示例:
输入:1->2->3->4->5->NULL
输出:5->4->3->2->1->NULL
进阶:你可以迭代或递归地反转链表。你能否用两种方法解决这道题?
数据结构定义
C
Python
思路
按照题目的要求, 今天给出两个思路, 个人觉得迭代会比较容易思考出来, 先给出迭代的思路.
迭代反转
迭代反转借助两个指针, 主指针用于遍历, 前向指针用于反转.
需要注意的是, 由于Python的独特赋值语句, 在进行指针赋值交换的时候, 一句语句即可实现,不需要借助临时变量保存待交换的变量, 同时, 利用这个特性也有助于加快程序运行速度, 读者应当熟练这个语法规则. 若觉得Python实现较难理解, 可以先看看C语言的实现.
此时head指针作为主指针移动,p指针记住head指针当前位置,head->next与pre指针实现反转, 迭代中反转的顺序是由前往后.
C实现
Python实现
递归反转
递归中则相反, 反转的顺序是由后往前. 主指针head->next遍历至尾部程序栈依次弹出, 依次反转直到回到第一个指针停止, 返回反转后的链表头指针.
如果你觉得代码比较难理解, 可以参考下面我绘制的图.
C实现
Python实现
领取专属 10元无门槛券
私享最新 技术干货