C语言链表逆序排列的算法有哪些 - 问答

在C语言中，实现链表逆序排列的方法有多种。以下是两种常见的算法：

迭代法（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;
}

递归法（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）。根据实际需求和资源限制，可以选择合适的算法来实现链表的逆序排列。

0 赞

0 踩