单链表反转的递归与非递归实现

# 1. 单链表的基本概念

在计算机科学中，链表是一种常见的数据结构，由一系列节点组成，每个节点包含数据元素和指向下一个节点的指针。链表与数组相比，具有动态插入和删除节点的优势，但访问元素的效率较低。链表可以分为单链表、双向链表和循环链表等不同类型。单链表是最简单的链表形式，其节点存储数据和下一个节点的指针。学习单链表的基本概念有助于理解更复杂的链表结构及相关算法。理解链表的特点和基本操作能够为日后的代码编写和问题解决提供基础，是数据结构和算法学习的重要一步。

# 2.1 创建单链表

在开始实现单链表常见操作之前，首先需要了解如何创建一个单链表。单链表由节点组成，每个节点包含数据和指向下一个节点的指针。创建一个单链表的过程可以分为以下几个步骤：

1. 定义节点类(Node)：首先定义一个节点类，节点类包含两个属性，数据部分和指针部分。数据部分用来存储节点的值，指针部分用来指向下一个节点。
2. 初始化头节点(head)：创建一个头节点，作为链表的起始点。头节点不存储实际数据，只是为了方便对链表的操作，初始时将头节点的指针指向空(null)。

3. 添加节点：按顺序向链表中添加节点。遍历链表，找到最后一个节点，然后在最后一个节点的指针部分指向一个新的节点。

4. 示例代码如下：

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = Node()

    def append(self, data):
        new_node = Node(data)
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = new_node

## 2.2 遍历单链表

遍历链表是指沿着链表的方向依次访问每个节点。遍历链表的过程需要从头节点开始，依次访问每个节点的数据，并移动到下一个节点，直到链表结束。

遍历链表的操作是很常见且基础的操作，在实现其他操作时也常常需要遍历链表。遍历链表的方法有多种，其中包括迭代遍历和递归遍历，下面将分别介绍这两种方法的实现过程。

### 2.2.1 迭代遍历

迭代遍历链表是使用循环的方式，从头节点开始，通过循环访问每个节点直到链表结束。每次迭代时，将当前节点的值输出，并移动到下一个节点，直到遍历完整个链表。

def iterate_linked_list(head):
    cur = head.next
    while cur is not None:
        print(cur.data)
        cur = cur.next

### 2.2.2 递归遍历

递归遍历链表是利用函数递归调用的方式，从头节点开始，先输出当前节点的值，然后递归调用遍历下一个节点，直到遍历完整个链表。

def recursive_linked_list(node):
    if node is None:
        return
    print(node.data)
    recursive_linked_list(node.next)

通过以上方法，我们可以实现对单链表的遍历操作，从而对链表中存储的数据进行访问和处理。

# 3