逆序建立链表（逆向链表）

## 逆序建立链表### 简介链表是一种常见的数据结构，由节点组成，每个节点包含数据和指向下一个节点的指针。建立链表通常是从头节点开始，依次添加节点。然而，在某些情况下，我们需要逆序建立链表，即先添加的节点在链表的尾部，后添加的节点在链表的头部。本文将详细介绍逆序建立链表的方法。### 方法逆序建立链表可以使用两种主要方法：1.

头插法:

每次将新节点插入到链表的头部，使其成为新的头节点。 2.

递归法:

使用递归函数，先处理后续节点，然后将当前节点插入到链表的头部。### 详细说明#### 1. 头插法1.

初始化:

创建一个空链表，并将头节点指针置为 NULL。 2.

循环添加节点:

- 创建一个新节点，并将其数据域设置为要添加的值。- 将新节点的指针域指向当前的头节点。- 将头节点指针更新为新节点。 3.

返回头节点:

循环结束后，头节点指针指向最后一个添加的节点，即逆序链表的头节点。

代码示例 (C语言):

```c #include #include struct Node {int data;struct Node

next; };struct Node

reverseBuildList() {struct Node

head = NULL;int data;printf("输入链表节点的值（输入-1结束）:\n");while (scanf("%d", &data) && data != -1) {struct Node

newNode = (struct Node

)malloc(sizeof(struct Node));newNode->data = data;newNode->next = head;head = newNode;}return head; }int main() {struct Node

head = reverseBuildList();// 打印链表printf("逆序建立的链表: ");struct Node

current = head;while (current != NULL) {printf("%d ", current->data);current = current->next;}printf("\n");return 0; } ```#### 2. 递归法1.

基本情况:

如果输入为空，则返回 NULL。 2.

递归步骤:

- 递归调用函数，处理后续节点，并将返回值作为当前节点的下一个节点。- 创建一个新节点，并将数据域设置为当前值。- 将新节点的指针域指向步骤 2.1 中得到的下一个节点。- 返回新节点。

代码示例 (Python):

```python class Node:def __init__(self, data):self.data = dataself.next = Nonedef reverseBuildList():data = input("输入链表节点的值（输入-1结束）: ")if data == '-1':return Noneelse:newNode = Node(int(data))newNode.next = reverseBuildList()return newNodehead = reverseBuildList()# 打印链表 print("逆序建立的链表:", end=" ") current = head while current is not None:print(current.data, end=" ")current = current.next print() ```### 总结逆序建立链表是一种常用的技巧，在处理需要反转顺序的数据时非常有用。本文介绍了两种实现方法：头插法和递归法。两种方法各有优劣，可以根据具体情况选择合适的方法。

逆序建立链表

简介链表是一种常见的数据结构，由节点组成，每个节点包含数据和指向下一个节点的指针。建立链表通常是从头节点开始，依次添加节点。然而，在某些情况下，我们需要逆序建立链表，即先添加的节点在链表的尾部，后添加的节点在链表的头部。本文将详细介绍逆序建立链表的方法。

方法逆序建立链表可以使用两种主要方法：1. **头插法:** 每次将新节点插入到链表的头部，使其成为新的头节点。 2. **递归法:** 使用递归函数，先处理后续节点，然后将当前节点插入到链表的头部。

详细说明

1. 头插法1. **初始化:** 创建一个空链表，并将头节点指针置为 NULL。 2. **循环添加节点:** - 创建一个新节点，并将其数据域设置为要添加的值。- 将新节点的指针域指向当前的头节点。- 将头节点指针更新为新节点。 3. **返回头节点:** 循环结束后，头节点指针指向最后一个添加的节点，即逆序链表的头节点。**代码示例 (C语言):**```c

include

include struct Node {int data;struct Node *next; };struct Node* reverseBuildList() {struct Node* head = NULL;int data;printf("输入链表节点的值（输入-1结束）:\n");while (scanf("%d", &data) && data != -1) {struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));newNode->data = data;newNode->next = head;head = newNode;}return head; }int main() {struct Node* head = reverseBuildList();// 打印链表printf("逆序建立的链表: ");struct Node* current = head;while (current != NULL) {printf("%d ", current->data);current = current->next;}printf("\n");return 0; } ```

2. 递归法1. **基本情况:** 如果输入为空，则返回 NULL。 2. **递归步骤:** - 递归调用函数，处理后续节点，并将返回值作为当前节点的下一个节点。- 创建一个新节点，并将数据域设置为当前值。- 将新节点的指针域指向步骤 2.1 中得到的下一个节点。- 返回新节点。**代码示例 (Python):**```python class Node:def __init__(self, data):self.data = dataself.next = Nonedef reverseBuildList():data = input("输入链表节点的值（输入-1结束）: ")if data == '-1':return Noneelse:newNode = Node(int(data))newNode.next = reverseBuildList()return newNodehead = reverseBuildList()

打印链表 print("逆序建立的链表:", end=" ") current = head while current is not None:print(current.data, end=" ")current = current.next print() ```

总结逆序建立链表是一种常用的技巧，在处理需要反转顺序的数据时非常有用。本文介绍了两种实现方法：头插法和递归法。两种方法各有优劣，可以根据具体情况选择合适的方法。