反转链表

题目描述

输入一个链表，反转链表后，输出新链表的表头。

思路

首先针对普通的情况，这里建立两个指针，pre和cur，分别表示前一节点和当前节点。对于当前节点，先将cur的下一个节点保存起来，然后转换指针方向，把cur指向pre。然后整体向后移动，pre移动到cur，cur移动到事先保存的cur的原本的next。此时移动后cur并没有指向pre。当再次处理当前cur时，cur会指向pre。
第二步就是考虑特殊情况，
1 表头是空，直接返回空
2 整个链表只有一个节点，返回这一个节点

代码

class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        if pHead is None:
            return None
        if pHead.next is None:
            return pHead
        pre = None
        cur = pHead
        while cur is not None: #A B->C 假设cur是B
            temp = cur.next #temp: C
            cur.next = pre #A <-B C
            pre = cur# pre 移到B
            cur = temp# cur移到C
            if cur is None: #pre到了尾部，cur是空
                return pre