Biegral Blog

      面试某公司，被问此题，由于紧张，程序有误，甚为遗憾！下面给出正确的程序：

#include<iostream>
using namespace std;

typedef struct node
{
	int data;
	struct node *next;
}Node, *List;

List createList()
{
	Node *head, *p1, *p2;
	p1 = p2 = head = new Node;

	int num;
	cin >> num;
	while(-1 != num)
	{
		p1 = new Node; 
		p1->data = num;
		p2->next = p1;
		p2 = p1;
		cin >> num;
	}
	p2->next = NULL;

	return head;
}

void printList(List p)
{
	while(NULL != p->next)
	{
		cout << p->next->data << " ";
		p = p->next;
	}
	cout << endl;
}

void releaseList(List p)
{
	if(NULL == p->next)
		delete p;
	else
	{
		releaseList(p->next);
		delete p;
	}
}

List reverseList(List p)
{
	//让p1和p2都指向第一个结点
	Node *p1 = p->next;
	Node *p2 = p1;
	
	p->next = NULL;//分离p与p1
	
	while(NULL != p1)
	{
		p2 = p1;
		p1 = p1->next; //在"摘下" p2时，千万记得先进行p1 = p1->next;

		//倒插法重建链表
		p2->next = p->next;
		p->next = p2;	
	}
	
	return p;
}

int main()
{
	List head = createList();
	printList(head);

	reverseList(head);
	printList(head);

	releaseList(head);

	return 0;
}