美文网首页
反转链表

反转链表

作者: Max_7 | 来源:发表于2018-10-04 17:41 被阅读0次

    题目描述

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

    思路

    首先针对普通的情况,这里建立两个指针,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
    

    相关文章

      网友评论

          本文标题:反转链表

          本文链接:https://www.haomeiwen.com/subject/qkwxaftx.html