写一c语言算法，实现对单链表就地逆置。

来源：百度知道 编辑：UC知道 时间：2024/06/07 17:52:17
试写一算法，对单链表实现就地逆置。

实现下列函数：
void Inverse(LinkList &L);
/* 对带头结点的单链表L实现就地逆置 */

单链表类型定义如下：
typedef struct LNode{
ElemType data;
struct LNode *next;
} LNode, *LinkList;

void inverse(LinkList &L)
{
LinkList h,p,q;
q=L;
p=h=L->next; //把q指向旧链表头，p，h指向第二个节点
while(p!=NULL) //倒置，把旧链表后一个节点的next指向前一个节点
{
h->next=q;
q=q->next;
p=p->next;
h=p;
}
L->next=NULL; //旧链表的头变成了新链表的尾，所以next为NULL
L=h； //把L指向新链表的头
}

//原来下面标1、2的地方位置错了，先改正
void Inverse(LinkList &L)
{
LinkList head=p=L,q;
while(p!=NULL)
{
q=head;
head=p;
p=p->next;//1
head->next=q;//2
}
L=head;
}

//这里不是假设L为单链表的第1个元素
//而是假设L->next为单链表的第1个元素
void Inverse(LinkList &L)
{
if(L->next==NULL)
return;
LNode* pNode;
LNode* pBuf=L;
while(pBuf->next!=NULL)
pBuf=pBuf->next;
while(L->next->next!=NULL){
pNode=L;
while(pNode->next->next!=NULL){
pNode=pNode->next;
}
pNode->next->next=pNode;
pNode->next=NULL;
}