【数据结构】带头节点的单链表逆置

川长思鸟来 2021-12-04 05:37 314阅读 0赞

#include<iostream>
    using namespace std;
    typedef struct LNode {
        int data;
        struct LNode *next;
    }LNode, *LinkList;
    
    bool InitList(LinkList &L) {
        L = new LNode;
        L->next = NULL;
        if (L)
            return true;
        return false;
    }
    
    // 创建链表（尾插法）
    void CreateList(LinkList &L) {
        LNode *p, *r = L;
        for (int i=0; i<10; i++) {
            p = new LNode;
            p->data = i;
            p->next = NULL;
            r->next = p;
            r = p;
        }
        r->next = NULL;
    }
    
    // 打印链表
    void PrintList(LinkList L) {
        cout<<"Head Node = "<<L<<endl;
        LNode *p = L->next;
        int i = 1;
        while (p) {
            cout<<"p" <<i<< "= "<<p<<" p->data = "<<p->data<<" p->next = "<<p->next<<endl;
            p = p->next;
            i++;
        }
        cout<<endl;
    }
    
    // 逆置单链表
    void ReverseList(LinkList &L) {
        LNode *head = L, *p, *q, *r;
        p = head->next;
        head->next = p->next;
        q = p;
        r = q, r->next = NULL;
        while (head->next) {
            p = head->next;
            head->next = p->next;
            q = p;
            q->next = r;
            r = q;
        }
        L->next = r;
    }
    
    int main() {
        LinkList L;
        InitList(L);
        CreateList(L);
    
        cout<<"逆置前"<<endl;
        PrintList(L);
    
        ReverseList(L);
        cout<<"逆置后"<<endl;
        PrintList(L);
    }

// 测试结果
    逆置前
    Head Node = 0x767f70
    p1= 0x767f80 p->data = 0 p->next = 0x767f90
    p2= 0x767f90 p->data = 1 p->next = 0x767fa0
    p3= 0x767fa0 p->data = 2 p->next = 0x767fb0
    p4= 0x767fb0 p->data = 3 p->next = 0x767fc0
    p5= 0x767fc0 p->data = 4 p->next = 0x767fd0
    p6= 0x767fd0 p->data = 5 p->next = 0x767ae0
    p7= 0x767ae0 p->data = 6 p->next = 0x767af0
    p8= 0x767af0 p->data = 7 p->next = 0x767b00
    p9= 0x767b00 p->data = 8 p->next = 0x767b10
    p10= 0x767b10 p->data = 9 p->next = 0
    
    逆置后
    Head Node = 0x767f70
    p1= 0x767b10 p->data = 9 p->next = 0x767b00
    p2= 0x767b00 p->data = 8 p->next = 0x767af0
    p3= 0x767af0 p->data = 7 p->next = 0x767ae0
    p4= 0x767ae0 p->data = 6 p->next = 0x767fd0
    p5= 0x767fd0 p->data = 5 p->next = 0x767fc0
    p6= 0x767fc0 p->data = 4 p->next = 0x767fb0
    p7= 0x767fb0 p->data = 3 p->next = 0x767fa0
    p8= 0x767fa0 p->data = 2 p->next = 0x767f90
    p9= 0x767f90 p->data = 1 p->next = 0x767f80
    p10= 0x767f80 p->data = 0 p->next = 0