学步园

        单链表的翻转是一道很基本的算法题。

        方法1：将单链表储存为数组，然后按照数组的索引逆序进行反转。

        方法2：使用三个指针遍历单链表，逐个链接点进行反转。

        方法3：从第2个节点到第N个节点，依次逐节点插入到第1个节点(head节点)之后，最后将第一个节点挪到新表的表尾。

       
方法1的问题是浪费空间。方法2和方法3效率相当。一般方法2较为常用。

方法2代码：

Node * ReverseList(Node *head)
{
	Node *p1,*p2,*p3;
	if(head==NULL||*head==NULL)
	return head;
	p1=head;
	p2=p1->next;
	while(p2)             //注意条件
	{
		p3=p2->next;	      //要改变p2->next的指针，所以必须先保留p2->next	     
		p2->next=p1;
		p1=p2;		      //循环往后
		p2=p3;
	}
	head->next=NULL;   //原先的head已经变成tail，别忘了置空，只有到这步才能置空
	*head=p1;
	return head;
}

方法3代码：

Node* ReverseList(Node* head) 
{ 
    Node *p,*q;  
    p=head->next; 
    while(p->next!=NULL)      //在这个循环过程中p所指的元素一直是不变的
	{
        q=p->next; 
        p->next=q->next; 
        q->next=head->next; 
        head->next=q; 
	} 
    p->next=head;            //相当于成环 
    head=p->next->next;       //新head变为原head的next 
    p->next->next=NULL;     //断掉环 
    return head;   
}

       附加一道题目，《编程之美》的3.4：从无头链表中删除节点。假设有一个没有头指针的单链表。一个指针指向此链表中间的一个节点（不是第一个，也不是最后一个节点），请将该节点从单链表中删除。

      
分析：无法知道前续的节点，只能知晓后续节点，所以存在一个难点，如何将前后两段连接起来。由于链表是要删除操作，所以多处一个可用空间。所以可以用翻转操作方法1的思想来解决。将需要删除节点的节点复制为其后续节点就可以了，这样后续节点已经不再链表中，可以进行析构。