算法练习：BM1 反转链表

题目内容

给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。

数据范围： 0 ≤ n ≤1000

要求：空间复杂度 O(1) ，时间复杂度 O(n) 。

如当输入链表{1,2,3}时，

经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。

我的思路

在遍历链表时，将当前节点的next 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。借用网上一个图解：

代码：

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head ListNode类 
# @return ListNode类
#
class Solution:
    def ReverseList(self , head: ListNode) -> ListNode:
        #如果head为空，则直接返回空
        if head is None:
            return head
            
        reverse_node = ListNode(head.val)
        x = head
        while x != None:
            if x.next != None:
                temp_node = ListNode(x.next.val)
                temp_node.next = reverse_node
                reverse_node = temp_node
            x = x.next
        return reverse_node

提交通过，但代码不够简洁。

参考答案

class Solution:
    def ReverseList(self , head: ListNode) -> ListNode:
        # write code here
        reverse = None
        phead = head
        while phead != None:
            tmp = phead.next
            phead.next = reverse
            reverse = phead
            phead = tmp
        return reverse

经验总结

• 我默认节点从第一个开始，就增加了判断的部分，还多调用一次构造函数
• 简洁的做法是，从第0个开始，默认节点为None，这样就省去了判断语句，逻辑更简单，语句简洁。