单链表逆置

写一个算法,借助栈将带头结点的单链表逆置。

将链表逆置,其实是将链表结点中的数据元素倒置,由于不知道链表的长度,可以用链栈来实现。扫描链表,将链表中数据元素依次进栈,然后,再一次扫描链表,同时依次进行出栈操作,将出栈的元素依次填到链表中去。

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; 
    } 
}

扩展资料栈的链接实现

发表评论

电子邮件地址不会被公开。 必填项已用*标注

昵称 *