[数据结构与算法]【数据结构】单链表逆置的详解

单链表的逆置

将单链表逆置：

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

//头文件
#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 <iostream>

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;i<n;i++){
        s=new Node;
        s->data=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<<p->data<<" ";
        p=p->next;
    }
    cout<<endl;
}

//逆置
void LinkList::inverseList(){
  //前指针
    Node *pre=NULL;
  //后指针 
   Node *rear=first;
  //工作指针
   Node *p=first;
   //p为空循环结束
    while(p){
        rear=rear->next; //后指针向后移动一个位置，防止摘链后再也找不到后继元素
        p->next=pre; //工作指针的指针域指向前一个元素 
        pre=p;
        p=rear;
    }
    first=pre; //最后一定要将头指针指向新的第一个元素
}