头插法实现链表逆置

链表逆置的头插法实现如下：

// 定义链表节点
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* reverseList(ListNode* head) {
    ListNode* newHead = nullptr;   // 新链表的头节点
    while (head != nullptr) {
        ListNode* next = head->next;  // 保存下一个节点的指针
        head->next = newHead;   // 将当前节点加入新链表头部
        newHead = head;  // 更新新链表头节点
        head = next;    // 更新原链表头节点
    }
    return newHead;
}

该函数的时间复杂度为 O(n)，其中 n 是链表的长度。

相关问题

头插法实现链表逆置的原理

链表逆置的头插法实现原理如下：

1. 定义一个新链表的头节点 newHead，初始值为 nullptr。

2. 遍历原链表，依次取出节点。

3. 对于每个取出的节点，将其插入到新链表的头部，即将其 next 指针指向 newHead，然后将 newHead 指向该节点，这样该节点就成为了新链表的头节点。

4. 重复步骤2-3，直到原链表的所有节点都被取出并插入到新链表中。

5. 返回新链表的头节点 newHead。

头插法逆置链表的优点是时间复杂度为 O(n)，相比于其他方法，它只需要遍历一次原链表即可完成逆置操作，因此具有较高的效率。

使用头插法实现链表逆置C语言

头插法是一种常用的链表逆置算法，它通过不断将当前遍历到的节点插入到链表的头部来实现链表的逆置。

以下是实现头插法逆置链表的 C 语言代码：

struct node {
    int data;
    struct node *next;
};

struct node* reverseList(struct node *head) {
    struct node *prev = NULL, *curr = head, *next = NULL;
    while (curr != NULL) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

在代码中，我们定义了一个名为 `node` 的结构体，用于存储链表中的节点。在 `reverseList` 函数中，我们使用三个指针 `prev`、`curr` 和 `next` 实现头插法，通过不断更新这三个指针的值，从而实现链表的逆置。最后，返回逆置后的链表的头节点。