单链表的逆转

单链表的逆转

法一： 就地逆置法

List Reverse( List L )
{
//L为链表的头节点
	if(L==NULL||L->Next==NULL)
	return L;//链表为空或只有一个节点
	List p=NULL,t=L;//p为存放逆置后的链表，t为工作指针，初始时指向头指针L 
	while(t!=NULL)
	{
		List temp;//标记指针 
		temp=t;
		t=t->Next;//工作指针后移  
		temp->Next=p;//承接上一个逆置的节点 
		p=temp;//存入逆置链表p 
	}
	return p;
}

方法二 头插法

算法思路：依次取原链表中的每一个节点，将其作为第一个节点插入到新链表中，指针用来指向当前节点，p为空时结束。

void reverse(List L)
{
	List p;
	p=L->next;
	L->next=NULL;
	while(p)
	{
		List q;//设置存放逆置的链表q 
		q=p;
		p=p->next;
		//头插 
		q->next=head->next;
		head->next=q;
	}
 }