单链表逆置
写一个算法,借助栈将带头结点的单链表逆置。
将链表逆置,其实是将链表结点中的数据元素倒置,由于不知道链表的长度,可以用链栈来实现。扫描链表,将链表中数据元素依次进栈,然后,再一次扫描链表,同时依次进行出栈操作,将出栈的元素依次填到链表中去。
void ReverseList(LinkList head) // head 是链表的头指针
{
LkStk *S;
InitStack(S); // 初始化链栈
Node *p; // p 是工作指针
p = head->next; // 初始时,p 指向首结点
while (p != NULL) { // 扫描链表,将链表中的数据元素依次进栈
Push(S, p->data);
p = p->next;
}
p = head->next;
while (! EmptyStack(S))
{
p->data = GetTop(S); // 取栈顶元素填入单链表中
Pop(S);
p = p->next;
}
}
扩展资料:栈的链接实现