反转单向链表

单向链表也叫单链表，是链表中最简单的一种形式，它的每个节点包含两个域，即元素域和链接域，其中，元素域用来存放具体的数据，而链接域则用来存放下一个节点的位置。

此外，单向链表中每个节点的链接域均指向另外一个节点，但最后一个节点的链接域则指向一个空值，如图19-2所示。

图19-2 单向链表

解析代码如下：

# 资源包\Code\chapter19\1934.py
# 链表的节点
class LinkedNode:
    def __init__(self, val):
        # 元素域
        self.val = val
        # 链接域
        self.next = None
# 定义四个节点
node1 = LinkedNode(1)
node2 = LinkedNode(2)
node3 = LinkedNode(3)
node4 = LinkedNode(4)
node1.next = node2
node2.next = node3
node3.next = node4
# 链表打印函数
def printLinkedList(header):
    node = header
    # 当节点为None，则表示链表元素已经遍历完毕
    while node:
        print(node.val, end=' ')
        node = node.next
    print()
# 输出正常顺序链表
printLinkedList(node1)
# 链表反转函数
def reverseLinkedList(header):
    # 如果链表为空，或者仅有一个元素，则返回
    if not header or not header.next:
        return header
    # 初始化上一个节点
    pre_node = None
    # 初始化下一个节点
    next_node = None
    while header:
        # 下一个节点为当前节点的下一个节点
        next_node = header.next
        # 将当前节点指向上一个节点
        header.next = pre_node
        # 上一个节点为当前节点
        pre_node = header
        # 将下一次遍历的节点换为当前节点的下一个节点
        header = next_node
    return pre_node
new_node = reverseLinkedList(node1)
printLinkedList(new_node)