一、题目描述：
输入一个链表，反转链表后，输出新链表的表头。
二、解题思路：
【双指针迭代】
1->2->3->4->5，遍历链表，把1的next置为None，2的next置为1，以此类推，5的next置为4。得到反转链表。需要考虑链表只有1个元素的情况。图中有具体的每步迭代的思路，最后输出pre而不是cur是因为最后一次迭代后cur已经指向None了，而pre是完整的反向链表。
（1）定义两个指针： pre 和 cur ；cur在前 ，pre在后。
（2）每次让 cur 的 next 指向 per ，实现一次局部反转
（3）局部反转完成之后， pre 和 cur 同时往前移动一个位置
（4）循环上述过程，直至 cur 到达链表尾部
三、解题代码：
class Solution:
# 返回ListNode
def ReverseList(self, pHead):
# write code here
## 空链表或只有一个节点得链表
if pHead==None or pHead.next==None:
return pHead
pre = None #指向空节点
cur = pHead #指向头节点
# 循环移动curent和pre，移动过程中反转 curent.next=pre
while cur: #while cur!=None:
tmp = cur.next #定义一个临时，指向当前结点的后续节点，防止链表断开
cur.next = pre #改变当前节点指向，指向pre 即反转
pre = cur #pre指向当前结点
cur = tmp #cur指向原有的后续节点，即保存在tmp中的节点
return pre #返回pre节点
复杂度分析：
1、时间复杂度O(N)：N表示链表长度，双指针一次遍历
2、空间复杂度O(1)：常数大小空间指针
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/99772.html
