赞
踩
单链表的逆置方法有很多种,此文简要说明以下三种方法
主要思路:遍历的过程中,将遍历的每一个元素依次插入到表头header之后
代码如下:
void ReverseList(LinkList& head)
{
LinkList p,q;
p = head->next;
head->next = NULL;
while (p)
{
q = p;
p = p->next;
q->next = head->next;
head->next = q;
}
}
主要思路:重新创建一个新表,遍历链表依次将元素插入到新表的头结点
代码如下:
void ReverseList(LinkList& L)
{
LinkList cur ,newlist, p;
cur = L->next;
newlist = NULL;
while(cur)
{
p = cur;
cur = cur->next;
p->next = newlist;
newlist = p;
}
L = newlist;
}
代码如下(示例):
Status ReverseList(ListLink L)
{
LinkList p = L;
if (p && p->next) //链表为空直接返回,而H->next为空是递归基
return p;
LinkList q = ReverseList(p->next); //一直循环到链尾
p->next->next = p; //翻转链表的指向
p->next = NULL; //记得赋值NULL,防止链表错乱
return q; //新链表头永远指向的是原链表的链尾
}
头插法和就地逆置法的区别在于,逆置后的链表输出时,那么头插法是从head开始的,而就地逆置则是从表尾开始的。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。