带头结点的单链表就地逆置

算法思路：

1. 定义三个指针prev、cur、next，分别指向头结点、头结点的下一个节点和下一个节点的下一个节点。

2. 将头结点的指针域置为NULL，表示反转后的链表末尾节点。

3. 循环遍历单链表，直到cur指向NULL，每次循环，将cur的指针域指向prev，表示将当前节点插入到反转后链表的头部。

4. 将prev指向cur，cur指向next，next指向next的下一个节点，继续遍历单链表。

5. 最后将头结点的指针域指向prev，完成链表的就地反转。

C++代码实现：

void reverseList(ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return;
    }

    ListNode *prev = head, *cur = head->next, *next = cur->next;
    prev->next = NULL;

    while (cur != NULL) {
        cur->next = prev;
        prev = cur;
        cur = next;
        if (next != NULL) {
            next = next->next;
        }
    }

    head->next = prev;
}

相关问题

带头结点单链表就地逆置

很高兴为您解答关于带头结点单链表就地逆置的问题。带头结点单链表的就地逆置可以通过从首节点开始反转每一个节点的指向，直到链表末尾完成。这里给出一个简单实现的C++代码：

#include<iostream>
using namespace std;

class ListNode{
public:
    int val;
    ListNode* next;
    ListNode(){}
    ListNode(int x): val(x), next(NULL){}
};

ListNode* reverseList(ListNode* head){
    if(head==NULL || head->next==NULL) return head;
    ListNode* pre = head;
    ListNode* cur = head->next;
    ListNode* nxt;
    pre->next = NULL;
    while(cur!=NULL){
        nxt = cur->next;
        cur->next = pre;
        pre = cur;
        cur = nxt;
    }
    return pre;
}

int main(){
    int n;
    cin>>n;
    ListNode* head = new ListNode(0);
    ListNode* p = head;
    for(int i=0;i<n;i++){
        int x; cin>>x;
        ListNode* node = new ListNode(x);
        p->next = node;
        p = p->next;
    }
    head = reverseList(head);
    p = head->next;
    while(p!=NULL){
        cout<<p->val<<" ";
        p = p->next;
    }
    cout<<endl;
    return 0;
}

该程序首先定义了一个ListNode类作为单链表的节点，然后定义了一个reverseList函数对带头结点的链表进行就地逆置。在main函数中，程序首先读入链表的长度n以及每个节点的值，然后通过一个循环将链表构建完成。接下来，我们对链表进行就地逆置，最后按照逆序输出每个节点的值。希望我的回答能够帮助到您，如有疑问，请随时追问。

用c语言实现编写实现带头结点单链表就地逆置的成员函数

下面是用C语言实现带头结点单链表就地逆置的成员函数的代码：

#include <stdio.h>
#include <stdlib.h>

// 定义单链表的结点结构体
typedef struct ListNode {
    int data;
    struct ListNode* next;
} ListNode;

// 初始化带头结点的单链表
ListNode* initList() {
    ListNode* head = (ListNode*)malloc(sizeof(ListNode));
    head->next = NULL;
    return head;
}

// 尾插法建立单链表
void createList(ListNode* head) {
    int data;
    ListNode* tail = head;
    printf("请输入链表中的元素（以-1结束）：");
    while (1) {
        scanf("%d", &data);
        if (data == -1) {
            break;
        }
        ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
        newNode->data = data;
        newNode->next = NULL;
        tail->next = newNode;
        tail = newNode;
    }
}

// 打印带头结点的单链表
void printList(ListNode* head) {
    ListNode* p = head->next;
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

// 就地逆置带头结点的单链表
void reverseList(ListNode* head) {
    ListNode* p = head->next;
    ListNode* q = p->next;
    p->next = NULL; // 将第一个结点的指针域赋值为NULL
    while (q != NULL) {
        ListNode* r = q->next;
        q->next = p;
        p = q;
        q = r;
    }
    head->next = p; // 将头结点的指针域指向原链表的最后一个结点
}

int main() {
    ListNode* head = initList();
    createList(head);
    printf("原链表：");
    printList(head);
    reverseList(head);
    printf("逆置后的链表：");
    printList(head);
    return 0;
}

运行结果：

请输入链表中的元素（以-1结束）：1 2 3 4 5 -1
原链表：1 2 3 4 5 
逆置后的链表：5 4 3 2 1