C++反转单向链表

单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部开始;链表是使用指针进行构造的列表;又称为结点列表,因为链表是由一个个结点组装起来的;其中每个结点都有指针成员变量指向列表中的下一个结点;列表是由结点构成,head指针指向第一个成为表头结点,而终止于最后一个指向nuLL的指针

单项列表的主要特点就是只知其子,不知其父。每个节点只能访问到它的下一个节点而访问不了它的上一个节点。

struct  Node {  int value;  Node* rbnext; };

这个简单的结构体构成了一个最简单的单链表节点

初始化

Node* pHead=new Node;

pHead->value=0;

pHead->rbnext=NULL;

Node* p=pHead;

for(int i=1;i<=5;i++)

{

p->rbnext=new Node;

p=p->rbnext;

p->value=i;

p->rbnext=NULL;

}

反转函数

void Reverse(Node*& pHead)

{

Node* p=pHead;//当前节点

Node* pBefore=NULL;// 上一个节点

Node* pNext=p->rbnext;//下一个节点

while(pNext!=NULL)

{

p->rbnext=pBefore;//当前节点的下一个节点为pBefore

pBefore=p;//pBefore设为当前节点

p=pNext;//当前节点移到下一个节点

pNext=pNext->rbnext;//下一个节点顺移

}

p->rbnext=pBefore;//最后一个节点赋值前一个下一个节点为pBefore

pHead=p;//最后赋值链表头

}

反转之前是 0 1 2 3 4 5

反转之后是 5 4 3 2 1 0

证明反转算法是正确的。

 

此条目发表在C++分类目录,贴了标签。将固定链接加入收藏夹。

发表评论