反转链表
2019-07-21 本文已影响0人
hustyanye
https://leetcode-cn.com/explore/interview/card/bytedance/244/linked-list-and-tree/1038/
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
思路就是对每个链表，对其进行就地逆序，比如1->2->3，对于2来说，把next指针指向1节点，在遍历过程中，注意：
- 用当前节点往前指一个，而不是将当前节点的下个节点指向当前节点
- 注意循环结束的条件！
- 注意返回值是pre，因为在遍历最后一个节点的时候，head已经指向他的next，即为None了，如果返回head就错了！
class Solution(object):
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head:
return None
pre = None
while head:
tmp = head.next
head.next = pre
pre = head
head = tmp
return pre
