亲宝软件园·资讯

展开

python单链表反转

xiaoming_tju 人气:0

代码如下:

class Node(object):
    def __init__(self, elem, next_=None):
        self.elem = elem
        self.next = next_
 
def reverseList(head):
    if head == None or head.next==None:  # 若链表为空或者仅一个数就直接返回
        return head 
    pre = None
    next = None
    while(head != None): 
        next = head.next     # 1
        head.next = pre     # 2
        pre = head      # 3
        head = next      # 4
    return pre

if __name__ == '__main__':
    l1 = Node(3)    # 建立链表3->2->1->9->None
    l1.next = Node(2)
    l1.next.next = Node(1)
    l1.next.next.next = Node(9)
    l = reverseList(l1)
    print (l.elem, l.next.elem, l.next.next.elem, l.next.next.next.elem)

原始单链表:

反转后单链表:

反转过程如下:

第一步:next = head.next
将 head.next 赋值给 next 变量,即next 指向了节点2,先将节点2 保存起来。

第二步:head.next = pre (初始pre==None)
将 pre 变量赋值给 head.next,即 此时节点1 指向了 None

第三步:pre = head
将 head 赋值给了 pre,即 pre 指向节点1,将节点1 设为“上一个节点”

第四步:head = next
将 next 赋值给 head,即 head 指向了节点2,此时节点2 设为“头节点”

第一次循环完毕,进入第二次循环,如下图:

第一步:next = head.next
将 head.next 赋值给 next 变量,即 next 指向了节点3,先将节点3 保存起来。

第二步:head.next = pre (此时的pre已经不为None)
将 pre 赋值给 head.next,pre 在上一次循环的时候指向了节点1,那么这一步的意义就是节点2 指向了 节点1,完成1和2节点的反转。

第三步:pre = head
将 head 赋值给了 pre,即 pre 指向节点2,将节点2 设为“上一个节点”

第四步:head = next
将 next 赋值给 head,即 head 指向了节点3。此时节点3 设为“头节点”

第二次循环完毕,以此类推!第三次第四次第五次循环。最后反转成如下图

若干注意点:

(1)帮助记忆图:

(2)当前头节点的下一个节点一定要保存(比如:当前头节点为2,先将节点3 保存起来)

(3)实现反转的key point: head.next = pre

加载全部内容

相关教程
猜你喜欢
用户评论