c语言利用单链表原来的节点空间逆转一个单链表

可以通过改变单链表节点的 next 指针的指向来实现单链表的逆转。具体实现方式如下：

void reverseLinkedList(Node* head) {
    Node *prev, *cur, *next;
    prev = NULL;
    cur = head;
    while (cur != NULL) {
        next = cur->next; // 先保存当前节点的下一个节点
        cur->next = prev; // 当前节点的 next 指针指向前一个节点
        prev = cur; // 更新前一个节点
        cur = next; // 更新当前节点
    }
}

在上述实现中，我们使用了三个指针：prev、cur 和 next。prev 指向当前节点的前一个节点，cur 指向当前节点，next 指向当前节点的下一个节点。每次循环先保存当前节点的下一个节点，然后将当前节点的 next 指针指向前一个节点，最后更新 prev、cur 和 next 的值。循环终止后，prev 指针指向原来链表的最后一个节点，即逆转后链表的头节点。因此，可以将原来链表的头节点改为 prev，实现单链表的逆转。

需要注意的是，上述实现方式只是改变了每个节点的 next 指针的指向，并没有改变节点本身的位置。因此，这种逆转方式利用了原来链表节点的空间，不需要额外的空间开销。

相关问题

设计一个算法，利用单链表原来的节点空间逆转一个单链表。要求用c语言实现

可以使用三个指针prev、curr、next来完成单链表的逆转，具体步骤如下：

1. 初始化prev指针为NULL，curr指针为链表头节点。
2. 循环遍历单链表，每次将curr指针指向的节点的next指针指向prev指针指向的节点，然后将prev指针指向curr指针指向的节点，curr指针指向原来节点的下一个节点。
3. 直到curr指针为NULL时，遍历结束，返回prev指针指向的节点，即为逆转后的链表头节点。

以下是C语言实现代码：

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

struct ListNode {
    int val;
    struct ListNode *next;
};

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

int main(){
    // 创建一个单链表
    struct ListNode *head = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->val = 1;
    head->next = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->next->val = 2;
    head->next->next = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->next->next->val = 3;
    head->next->next->next = NULL;
    
    // 输出原来的单链表
    printf("Original List: ");
    struct ListNode *curr = head;
    while(curr != NULL){
        printf("%d ", curr->val);
        curr = curr->next;
    }
    printf("\n");
    
    // 逆转单链表
    struct ListNode *newHead = reverseList(head);
    
    // 输出逆转后的单链表
    printf("Reversed List: ");
    curr = newHead;
    while(curr != NULL){
        printf("%d ", curr->val);
        curr = curr->next;
    }
    printf("\n");
    
    return 0;
}

输出结果为：

Original List: 1 2 3 
Reversed List: 3 2 1 

用C语言设计一个算法，利用单链表原来的结点空间逆转一个单链表

可以使用三个指针prev, current和next，分别指向当前节点的前一个节点、当前节点和下一个节点，然后依次遍历单链表，将每个节点的指针指向前一个节点，最后返回新的头节点即可。

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

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

// 定义单链表节点
struct Node {
    int data;
    struct Node* next;
};

// 反转单链表
struct Node* reverseLinkedList(struct Node* head) {
    struct Node *prev, *current, *next;
    prev = NULL;
    current = head;
    while (current != NULL) {
        next = current->next; // 保存下一个节点
        current->next = prev; // 当前节点指向前一个节点
        prev = current; // 前一个节点更新为当前节点
        current = next; // 当前节点更新为下一个节点
    }
    return prev; // 新的头节点为原来的尾节点
}

// 打印单链表
void printLinkedList(struct Node* head) {
    struct Node* current = head;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

int main() {
    // 创建单链表
    struct Node* head = (struct Node*)malloc(sizeof(struct Node));
    head->data = 1;
    head->next = (struct Node*)malloc(sizeof(struct Node));
    head->next->data = 2;
    head->next->next = (struct Node*)malloc(sizeof(struct Node));
    head->next->next->data = 3;
    head->next->next->next = NULL;

    // 打印原来的单链表
    printf("Original linked list: ");
    printLinkedList(head);

    // 反转单链表
    head = reverseLinkedList(head);

    // 打印反转后的单链表
    printf("Reversed linked list: ");
    printLinkedList(head);

    return 0;
}

运行结果：

Original linked list: 1 2 3 
Reversed linked list: 3 2 1