华为云国际站代理商：c语言链表逆置思想

luotuoemo • 2024年4月7日 21:39 • 华为云 • 阅读 337

在C语言中，对链表进行逆置是数据结构中的一个基础操作，它要求将链表的节点顺序完全颠倒。链表逆置的思想可以根据不同的算法有不同的实现方式，以下是几种常见的方法：

方法1：迭代法

迭代法是实现链表逆置的一种直观方法。在遍历链表的过程中，逐个修改每个节点的指针方向，直至全部节点的指向被反转。

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* prev = NULL;
    struct ListNode* curr = head;
    while (curr != NULL) {
        struct ListNode* nextTemp = curr->next; // 临时保存当前节点的下一个节点
        curr->next = prev;  // 反转当前节点的指针
        prev = curr;  // 前进
        curr = nextTemp;  // 前进
    }
    return prev;
}

方法2：递归法

递归法的基本思想是将链表看作两部分：第一个节点和剩余的节点。首先递归反转剩余的节点，然后将原链表的头节点添加到反转后的链表的末尾。

struct ListNode* reverseList(struct ListNode* head) {
    if (head == NULL || head->next == NULL) return head;
    struct ListNode* p = reverseList(head->next);
    head->next->next = head; // 反转
    head->next = NULL; // 断开原来的连接
    return p;
}

方法3：头插法

头插法是一种特殊的迭代方法，其基本思想是在遍历原链表的过程中，将每个遍历到的节点插入到一个新链表的头部，从而实现逆置。

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* newHead = NULL; // 新链表的头节点
    while (head != NULL) {
        struct ListNode* next = head->next;
        head->next = newHead; // 将当前节点插入新链表头部
        newHead = head;
        head = next;
    }
    return newHead;
}

以上是C语言实现链表逆置的几种基本方法。每种方法都有其优缺点，但从根本上说，它们都运用了重新指向或者重新连接节点的思想来实现链表的逆置。选择哪种方法取决于具体的应用场景和个人偏好。

逆置链表是数据结构中常见的问题之一，其主要目标是将原链表的节点顺序逆转。对于C语言实现的链表来说，链表逆置可以通过几种方法实现，比如迭代法、递归法和头插法。下面以迭代法和头插法两种思想说明逆置链表的实现。

1. 迭代法

这种方法需要跟踪当前节点、它的前一个节点和它的下一个节点。算法逐个遍历链表的节点，并在访问每个节点时，调整它的指针方向，使其指向前一个节点。

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

struct ListNode* reverseListIterative(struct ListNode* head) {
    struct ListNode *prev = NULL;
    struct ListNode *current = head;
    while (current) {
        // 保存当前节点的下一个节点
        struct ListNode *nextTemp = current->next;
        // 更改当前节点指针，指向它的前一个节点
        current->next = prev;
        // 更新prev和current指针，向前移动
        prev = current;
        current = nextTemp;
    }
    return prev; // 最后prev将成为新链表的头部
}

2. 头插法

头插法是一种高效的链表逆置方法，它利用头节点来逐个将原链表中的元素重新插入到一个新的链表中，每次都插入到头部，最终得到的新链表则是原链表的逆置。这种方法不需要额外追踪前一个节点，因此逻辑更为简单直观。

struct ListNode* reverseListHeadInsert(struct ListNode* head) {
    struct ListNode *newHead = NULL;
    while (head) {
        struct ListNode *next = head->next; // 保存下一个节点
        head->next = newHead; // 将当前节点的下一个节点指向新链表的头部
        newHead = head; // 更新新链表的头部为当前节点
        head = next; // 继续处理原链表的下一个节点
    }
    return newHead;
}