LeetCode 每日一题206：反转链表

提前祝大家春节快乐~

题目

反转一个单链表。

示例:

输入: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实现