【数据结构】单链表逆置的详解

将单链表逆置：

定义一个前指针和一个后指针用来辅助工作指针

//头文件
#ifndef linkLIST_H_INCLUDED
#define linkLIST_H_INCLUDED


struct Node{
    int data; //数据域
    Node *next; //指针域
};

class linkList{
public:
    linkList(int *arr,int n);  //构造函数 尾插法
    ~linkList();		//析构函数
    void printList();	//打印单链表
    void inverseList();	//逆置单链表
private:
    Node *first;	//头指针
};

#endif // linkLIST_H_INCLUDED

#include "linkList.h"
#include 

using namespace std;

linkList::linkList(int *arr,int n){
    first=new Node;
    Node *s=NULL;
	//无头结点
    first->data=arr[0];
    Node *rear=first;
    for(int i=1;idata=arr[i];
        rear->next=s;
        rear=s;
    }
    rear->next=NULL;
}

linkList::~linkList(){
    Node *p=first;
    while(p){
        first=first->next;
        delete p;
        p=first;
    }
}

void linkList::printList(){
    Node *p=first;
    while(p){
        cout<data<<" ";
        p=p->next;
    }
    cout<next; //后指针向后移动一个位置，防止摘链后再也找不到后继元素
        p->next=pre; //工作指针的指针域指向前一个元素 
        pre=p;
        p=rear;
    }
    first=pre; //最后一定要将头指针指向新的第一个元素
}