在C語言中,實現鏈表逆序排列的方法有多種。以下是兩種常見的算法:
迭代法的基本思想是使用三個指針,分別指向當前節點、前一個節點和后一個節點。通過遍歷鏈表,將當前節點的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;
}
遞歸法的基本思想是先遞歸地反轉鏈表的子鏈表,然后將當前節點添加到反轉后的子鏈表的末尾。
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)。根據實際需求和資源限制,可以選擇合適的算法來實現鏈表的逆序排列。