使用头插法实现链表逆置C语言

头插法是一种常用的链表逆置算法，它通过不断将当前遍历到的节点插入到链表的头部来实现链表的逆置。

以下是实现头插法逆置链表的 C 语言代码：

struct node {
    int data;
    struct node *next;
};

struct node* reverseList(struct node *head) {
    struct node *prev = NULL, *curr = head, *next = NULL;
    while (curr != NULL) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

在代码中，我们定义了一个名为 `node` 的结构体，用于存储链表中的节点。在 `reverseList` 函数中，我们使用三个指针 `prev`、`curr` 和 `next` 实现头插法，通过不断更新这三个指针的值，从而实现链表的逆置。最后，返回逆置后的链表的头节点。

相关问题

使用头插法实现链表逆置C语言的步骤

### 回答1：
头插法实现链表逆置的步骤如下:

1. 定义一个空的新链表作为结果链表。

2. 从原链表的头开始遍历，将每个节点的数据插入到新链表的头部。

3. 重复步骤2直到遍历完整个原链表。

4. 将新链表的头节点设置为原链表的头节点。

代码示例:

struct node {
   int data;
   struct node *next;
};

void reverse(struct node** head_ref)
{
    struct node* prev = NULL;
    struct node* current = *head_ref;
    struct node* next = NULL;
    while (current != NULL) {
        next  = current->next;  
        current->next = prev;   
        prev = current;
        current = next;
    }
    *head_ref = prev;
}

### 回答2：
使用头插法实现链表逆置的步骤如下：

1. 声明一个指向链表结点的指针变量head，表示头结点。
2. 创建一个新的链表结点newNode，并将其数据域初始化为链表的第一个结点的数据域。
3. 将新结点newNode的next指针指向head指针的指向的结点。
4. 将head指向新结点newNode，使得head指向链表的第一个结点。
5. 重复步骤2至步骤4，直到遍历完整个链表。
6. 由于头插法是将每个结点插入到头结点之后，最终完成逆置后，原链表的第一个结点会变成逆置后链表的最后一个结点，因此需要将其next指针置为空。
7. 返回逆置后的头结点head。

例如，对于链表1 -> 2 -> 3 -> 4 -> NULL，使用头插法逆置后，得到逆置后的链表为4 -> 3 -> 2 -> 1 -> NULL。具体的C语言代码实现如下：

#include<stdio.h>
#include<stdlib.h>

typedef struct ListNode {
    int data;
    struct ListNode* next;
} ListNode;

ListNode* reverseList(ListNode* head) {
    ListNode* currentNode = head;
    ListNode* newHead = NULL;

    while (currentNode != NULL) {
        ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
        newNode->data = currentNode->data;
        newNode->next = newHead;
        newHead = newNode;
        currentNode = currentNode->next;
    }

    return newHead;
}

int main() {
    // 创建链表1 -> 2 -> 3 -> 4 -> NULL
    ListNode* node4 = (ListNode*)malloc(sizeof(ListNode));
    node4->data = 4;
    node4->next = NULL;
    ListNode* node3 = (ListNode*)malloc(sizeof(ListNode));
    node3->data = 3;
    node3->next = node4;
    ListNode* node2 = (ListNode*)malloc(sizeof(ListNode));
    node2->data = 2;
    node2->next = node3;
    ListNode* node1 = (ListNode*)malloc(sizeof(ListNode));
    node1->data = 1;
    node1->next = node2;

    // 输出原链表
    ListNode* current = node1;
    printf("原链表：");
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");

    // 逆置链表
    ListNode* reversedHead = reverseList(node1);

    // 输出逆置后的链表
    current = reversedHead;
    printf("逆置后的链表：");
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");

    return 0;
}

运行该程序，可以看到输出结果为：

原链表：1 -> 2 -> 3 -> 4 -> NULL
逆置后的链表：4 -> 3 -> 2 -> 1 -> NULL

### 回答3：
头插法是一种常用的链表逆置方法，可以通过以下步骤来实现：

1. 定义链表节点的结构体，包含一个数据域和一个指向下一节点的指针域。
2. 创建链表的头指针，并初始化为空。
3. 通过循环，依次读入输入的数据，并创建新的节点。
4. 将新节点的指针域指向链表的第一个节点，并将头指针指向新节点。即将新节点插入到链表的头部。
5. 重复步骤3和步骤4，直到读入所有的数据。
6. 遍历链表，输出逆置后的链表。

以下是一个具体的代码示例：

#include <stdio.h>
#include <stdlib.h>

// 定义链表节点的结构体
typedef struct ListNode {
    int data;
    struct ListNode* next;
} ListNode;

// 创建新节点并初始化
ListNode* createNode(int data) {
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 使用头插法逆置链表
ListNode* reverseList(ListNode* head) {
    ListNode* newHead = NULL;
    ListNode* currentNode = head;
    
    while(currentNode != NULL) {
        ListNode* nextNode = currentNode->next;
        
        currentNode->next = newHead;
        newHead = currentNode;
        
        currentNode = nextNode;
    }
    
    return newHead;
}

int main() {
    ListNode* head = NULL;
    int num;
    
    printf("请输入要创建链表的节点数：");
    scanf("%d", &num);
    
    printf("请输入要创建链表的节点数据：\n");
    for(int i = 0; i < num; i++) {
        int data;
        scanf("%d", &data);
        
        ListNode* newNode = createNode(data);
        newNode->next = head;
        head = newNode;
    }
    
    printf("原始链表：\n");
    ListNode* currentNode = head;
    while(currentNode != NULL) {
        printf("%d ", currentNode->data);
        currentNode = currentNode->next;
    }
    
    ListNode* newHead = reverseList(head);
    printf("\n逆置后的链表：\n");
    currentNode = newHead;
    while(currentNode != NULL) {
        printf("%d ", currentNode->data);
        currentNode = currentNode->next;
    }
    
    return 0;
}

以上代码会先依次读入节点个数和节点数据，并创建一个包含这些节点的链表。然后使用头插法方法逆置链表，并输出逆置后的结果。

使用插入法实现链表逆置C语言

可以使用插入法来实现链表的逆置，具体步骤如下：

1. 创建一个新的空链表，用于存储逆置后的数据。
2. 取出原链表的第一个节点，将其插入新链表的最前端。
3. 将原链表的第二个节点插入新链表的第二个位置。
4. 重复步骤3，直到原链表中的所有节点都插入到了新链表中。
5. 返回新链表的头指针，作为逆置后的链表。

以下是 C 语言代码的实现：

struct node {
  int data;
  struct node *next;
};

struct node *reverseList(struct node *head) {
  struct node *new_head = NULL;

  while (head != NULL) {
    struct node *temp = head;
    head = head->next;

    temp->next = new_head;
    new_head = temp;
  }

  return new_head;
}