数据结构 链表的逆置(经典重点题!!)
---------------start reading---------------
链表逆置就是把最后以一个提到坐前面,倒数第二个放到第二个……直到第一个到最后一个。
由于链表没有下标,所以不能借助下表来实行数据的逆置,要靠空间的转移来完成链表的逆置
方法一
利用头插思想(最重要!)
将头节点提出来,将第一个数据结点next置成NULL进行头插,再将第二个数据结点进行头插,第三个数据结点进行头插……直到最后一个数据结点头插进链表。
这里利用了头插的特性,在进行头插的时候如果插入1-5结果就显示5、4、3、2、1,所以我们将整个链表再进行头插链表就可以逆置,变成1、2、3、4、5.
具体操作如下
void Reverse(List plist)//考试的重点内容
{
if(plist==NULL || plist->next==NULL || plist->next->next==NULL)
{
return ;
}
//下面的时间复杂度为O(n),并且最好,利用头插的思想
Node *p = plist->next;
Node *q;
plist->next = NULL;//
while(p != NULL)
{
q = p->next;
p->next = plist->next;//将节点p头插到链表中
plist->next = p;
p = q;
}
}
方法二
改变数据(表面改变)
这个方法有点偷懒,我们不改变链表的结构,直接变数据,因为链表引用最后是显示在数据上的,所以我们可以定义一个临时变量tmp,交换首尾数据,再交换第二个和倒数第二个数据……知道走到中间
具体操作如下
void Reverse(List plist)//考试的重点内容
{
if(plist==NULL || plist->next==NULL || plist->next->next==NULL)
{
return ;
}
//下面方法的时间复杂度为O(n^2)
Node *p = plist->next;
Node *q;
int tmp;
for(q=plist;q->next!=NULL;q=q->next) ;
for(int i=0;i<GetLength(plist)/2;i++)
{
tmp = p->data;
p->data = q->data;
q->data = tmp;
p = p->next;
q = GetPri(plist,q);//前面博客单链表的基本操作中有获得前驱的函数
//时间复杂度为O(n)
}
}
方法三
利用双向链表(交换数据)双向链表相关知识请参考之前的博客
因为双向链表有前驱,所以和方法二同样的方式,交换数据,但可以不用找前驱的函数,时间复杂度为O(n)。
具体操作如下
typedef struct DNode
{
int data;
struct DNode *next;//后继指针
struct DNode *prio;//前驱指针
}DNode,*DList;
void Reverse(DList plist)
{
if(plist==NULL || plist->next==NULL || plist->next->next==NULL)//没有数据或者只有一个数据不逆置
{
return ;
}
int len = GetLength(plist);
int tmp;
DNode *p = plist->next; // p找到第一个数据节点
DNode *q;
for(q=plist->next;q->next != NULL;q=q->next) ; // q找到尾节点
for(int i=0;i<len/2;i++)
{
tmp = p->data;
p->data = q->data;
q->data = tmp;
p = p->next;
q = q->prio;
}
}
逆置还有很多优秀的方法,目前先分享三种,方法一的思想和操作一定要掌握鸭!