给出带头结点与不带头结点的单链表逆置几种方法

带头结点的单链表逆置可以通过以下几种方法实现：

1. 迭代法：从头结点开始，依次将每一个节点的 next 指针指向前一个节点，直到链表末尾。同时需要记录下一个节点的指针，以便进行下一次迭代。最后将头结点的 next 指针指向空节点，并将原链表的最后一个节点作为新的头结点。时间复杂度为 O(n)，空间复杂度为 O(1)。

2. 递归法：采用递归的方式，先逆置除头结点之外的子链表，再将头结点插入到逆置后的子链表的尾部。时间复杂度为 O(n)，空间复杂度为 O(n)，因为递归调用需要消耗栈空间。

不带头结点的单链表逆置可以通过以下几种方法实现：

1. 迭代法：与带头结点的方法类似，只需从第一个节点开始进行逆置即可。时间复杂度为 O(n)，空间复杂度为 O(1)。

2. 递归法：由于没有头结点，递归法需要特殊处理链表为空或只有一个节点的情况。对于多个节点的情况，可以将第一个节点与后面的子链表逆置，然后将第一个节点插入到逆置后的子链表的尾部。时间复杂度为 O(n)，空间复杂度为 O(n)。

相关问题

将不带头结点的单链表逆置

好的，我可以为您提供一个简单的算法来将不带头结点的单链表逆置。具体的实现方法如下：

1. 从原链表的头结点开始，定义三个指针pre、p和next，其中pre指向NULL，p指向头结点，next指向p的下一个结点。

2. 反复执行下列操作，直到p指向NULL：

(1) 将p的下一个结点指向pre，即p->next=pre;

(2) 将pre向右移动，即pre=p;

(3) 将p向右移动，即p=next;

(4) 将next向右移动，即next=p->next;

3. 最后将原链表的尾结点指向NULL，并将逆置后的链表的头结点指向原链表的尾结点。

下面是具体的代码实现：

void ReverseList(Node* head) {

Node* pre = NULL;
Node* p = head;
Node* next = p->next;

while (p != NULL) {
p->next = pre;
pre = p;
p = next;
if (next != NULL) {
next = next->next;
}
}

head->next = NULL;
head = pre;
}

希望我的回答对您有所帮助，如果您有其他问题，也欢迎随时提出。

带头结点的单链表逆置

以下是带头结点的单链表逆置的 C++ 代码实现：

#include <iostream>
using namespace std;

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

// 定义链表逆置函数
ListNode* reverseList(ListNode* head) {
    ListNode* prev = NULL;
    ListNode* curr = head->next;
    while (curr) {
        ListNode* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    head->next = prev;
    return head;
}

// 测试
int main() {
    ListNode* head = new ListNode(0);
    ListNode* p1 = new ListNode(1);
    ListNode* p2 = new ListNode(2);
    ListNode* p3 = new ListNode(3);
    head->next = p1;
    p1->next = p2;
    p2->next = p3;
    cout << "原链表：";
    for (ListNode* p = head->next; p; p = p->next) {
        cout << p->val << " ";
    }
    cout << endl;
    head = reverseList(head);
    cout << "逆置后链表：";
    for (ListNode* p = head->next; p; p = p->next) {
        cout << p->val << " ";
    }
    cout << endl;
    return 0;
}

该代码中，reverseList 函数实现了链表的逆置操作，head 为带头结点的链表头。在逆置过程中，需要用到三个指针 prev、curr 和 next，分别表示前驱结点、当前结点和后继结点。具体实现方式是，每次将 curr 结点的 next 指针指向 prev，然后将 prev、curr 和 next 分别后移一个结点，直到 curr 结点为空。最后将头结点的 next 指针指向逆置后的链表头结点 prev。