反转单向链表Python版

193 30天之前 Python 链表

答案

链表节点定义:

class Node(object):
    def __init__(self):
        self.value = None
        self.next = None

链表反转:

def reverse_linked_list(head):
    if not head or not head.next:
        return head

    prev = None            # 用于暂存前面的节点
    next = None            # 用于暂存前面的节点
    while head:
        next = head.next   # 缓存当前节点的向后指针,待下次迭代用
        head.next = prev   # 这一步是反转的关键,相当于把当前的向前指针作为当前节点的向后指针
        prev = head        # 作为下次迭代时的(当前节点的)向前指针
        head = next        # 作为下次迭代时的(当前)节点

    return prev            # 返回头指针,头指针就是迭代到最后一次时的head变量(赋值给了pre)

答案解析

构建一个 0 -> 1 -> 2 -> 3 的链表,然后反转:

if __name__ == '__main__':
    three = Node()
    three.value = 3

    two = Node()
    two.value = 2
    two.next = three

    one = Node()
    one.value = 1
    one.next = two

    head = Node()
    head.value = 0
    head.next = one

    new_head = reverse_linked_list(head)
    while new_head:
        print(new_head.value)
        new_head = new_head.next

输出:

3
2
1
0