C語言鏈表逆序排列的算法有哪些

在C語言中，實現鏈表逆序排列的方法有多種。以下是兩種常見的算法：

1. 迭代法（Iterative）

迭代法的基本思想是使用三個指針，分別指向當前節點、前一個節點和后一個節點。通過遍歷鏈表，將當前節點的next指針指向前一個節點，然后更新三個指針的位置。最后，將原鏈表的頭節點指向新的頭節點。

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

Node* reverseList(Node* head) {
    Node* prev = NULL;
    Node* current = head;
    Node* next = NULL;

    while (current != NULL) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }

    return prev;
}

2. 遞歸法（Recursive）

遞歸法的基本思想是先遞歸地反轉鏈表的子鏈表，然后將當前節點添加到反轉后的子鏈表的末尾。

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

Node* reverseListHelper(Node* node, Node* prev) {
    if (node == NULL) {
        return prev;
    }

    Node* next = node->next;
    node->next = prev;
    return reverseListHelper(next, node);
}

Node* reverseList(Node* head) {
    return reverseListHelper(head, NULL);
}

這兩種方法都可以實現鏈表的逆序排列。迭代法的時間復雜度為O(n)，空間復雜度為O(1)；遞歸法的時間復雜度為O(n)，空間復雜度為O(n)（遞歸調用棧的深度為n）。根據實際需求和資源限制，可以選擇合適的算法來實現鏈表的逆序排列。