单链表倒置算法和二叉树的遍历
2016-05-21 本文已影响223人
赤赤有名
void reverse(list *head)
{
list *p, *q;
p = head->next;//p指向当前正在处理的节点
q = p->next;//tmp指向尚未被处理的第一个节点
p->next = NULL;//原单链表第一个节点将成为倒置后最后一个节点
head->next = p;//插入单链表表头后面
p = q;//开始处理接下来的节点们
while(p) {
q = p->next;
p->next = head->next;
head->next = p;
p = q;
}
}
（头结点不算，从第一个节点开始）
思想是，遍历整个链表的同时，将正在访问的节点插入到链表头部。
这样，当遍历结束后，同时完成了链表的倒置。
方法二：
LinkList reverse(LinkList L)//单链表的倒置算法
{
LNode*p,*q;
p=L->next;
L->next=NULL;
while(p)
{
q=p;
p=p->next;
q->next=L->next;
L->next=q;
}
returnL;
}
