C语言 只使用两个指针反转一个单向链表

1、使用两个指针反转链表

可以只使用两个指针反转一个单向链表，但逻辑会稍微复杂一点。我们可以通过巧妙地在迭代过程中更新指针，达到反转链表的效果。

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

// 定义节点结构
struct Node {
    int data;
    struct Node* next;
};

// 创建新节点
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 反转链表（使用两个指针）
struct Node* reverseList(struct Node* head) {
    struct Node* prev = NULL;
    struct Node* curr = head;

    while (curr != NULL) {
        struct Node* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }

    return prev;
}

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

// 释放链表
void freeList(struct Node* head) {
    while (head != NULL) {
        struct Node* temp = head;
        head = head->next;
        free(temp);
    }
}

int main() {
    // 创建链表 1->2->3->4->NULL
    struct Node* head = createNode(1);
    head->next = createNode(2);
    head->next->next = createNode(3);
    head->next->next->next = createNode(4);

    printf("原始链表: ");
    printList(head);

    // 反转链表
    head = reverseList(head);

    printf("反转后的链表: ");
    printList(head);

    // 释放内存
    freeList(head);

    return 0;
}

标准写法略作修改

在每次循环中用一个临时变量交换两个指针的含义，达到节省第三个指针的目的。

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

// 定义节点结构
struct Node {
    int data;
    struct Node* next;
};

// 创建新节点
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 反转链表（使用两个指针）
struct Node* reverseList(struct Node* head) {
    struct Node* prev = NULL;
    struct Node* curr = head;

    while (curr) {
        curr = (struct Node*)((uintptr_t)curr->next ^ (uintptr_t)prev);
        // 上面是技巧性的 XOR 计算。不是推荐方式。
    }

    return prev;
}


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

// 释放链表
void freeList(struct Node* head) {
    while (head != NULL) {
        struct Node* temp = head;
        head = head->next;
        free(temp);
    }
}

int main() {
    // 创建链表 1->2->3->4->NULL
    struct Node* head = createNode(1);
    head->next = createNode(2);
    head->next->next = createNode(3);
    head->next->next->next = createNode(4);

    printf("原始链表: ");
    printList(head);

    // 反转链表
    head = reverseList(head);

    printf("反转后的链表: ");
    printList(head);

    // 释放内存
    freeList(head);

    return 0;
}

2、 更清晰、可读的标准方式（推荐使用三个指针）

使用三个指针 (previous, current, next) 的标准方式通常被认为更清晰和可读，因为它在每一步都显式地维护了当前节点、前一个节点和下一个节点的引用，使得链表的反转过程更加直观易懂。

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

// 定义节点结构
struct Node {
    int data;
    struct Node* next;
};

// 创建新节点
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 反转链表（三个指针）
struct Node* reverseList(struct Node* head) {
    struct Node* prev = NULL;
    struct Node* curr = head;
    struct Node* next = NULL;

    while (curr != NULL) {
        next = curr->next;   // 暂存下一个节点
        curr->next = prev;   // 反转指针
        prev = curr;         // 向前推进
        curr = next;
    }

    return prev;  // 新的头结点
}



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

// 释放链表
void freeList(struct Node* head) {
    while (head != NULL) {
        struct Node* temp = head;
        head = head->next;
        free(temp);
    }
}

int main() {
    // 创建链表 1->2->3->4->NULL
    struct Node* head = createNode(1);
    head->next = createNode(2);
    head->next->next = createNode(3);
    head->next->next->next = createNode(4);

    printf("原始链表: ");
    printList(head);

    // 反转链表
    head = reverseList(head);

    printf("反转后的链表: ");
    printList(head);

    // 释放内存
    freeList(head);

    return 0;
}