学步园

题目：输入一个链表的头结点，反转该链表，并返回反转后链表的头结点。

分两种情况：带头结点的链表，不带头结点的链表

#include "stdafx.h"
#include<iostream>
#include<algorithm>
using namespace std;

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

List createListWithHead(int n)//创建带头结点的链表
{
	List head = (List)malloc(sizeof(Node));
	head->data = 0;
	head->next = NULL;

	List p = head;
	for(int i=0;i<n;i++)
	{
		List no = (List)malloc(sizeof(Node));
		no->data = i+1;
		no->next = NULL;

		p->next = no;
		p = no;
	}
	return head;
}

List createListWithOutHead(int n)//创建不带头结点的链表
{
	if(n==0)
		return NULL;
	List head = (List)malloc(sizeof(Node));
	head->data = 1;
	head->next = NULL;
	List p = head;
	for(int i=2;i<=n;i++)
	{
		List q = (List)malloc(sizeof(Node));
		q->data = i;
		q->next = NULL;
		
		p->next = q;
		p = q;
	}
	return head;
}

void traverseWithHead(List head)//遍历带头结点的链表
{
	if(head == NULL)
		return;
	List p = head->next;
	while(p)
	{
		cout<<p->data<<" ";
		p = p->next;
	}
	cout<<endl;
}

void traverseWithOutHead(List head)//遍历不带头结点的链表
{
	if(head == NULL)
		return ;
	List p = head;
	while(p)
	{
		cout<<p->data<<" ";
		p = p->next;
	}
	cout<<endl;
}

void reverseWithHead(List head)//翻转带头结点的链表
{
	if(head==NULL ||head->next==NULL)
		return;
	List p = head->next;
	List q = p->next;
	while(q)
	{
		p->next = q->next;
		q->next = head->next;
		head->next = q;
		//p = p->next;
		q = p->next;	
	}
}

//翻转不带头结点的链表,这里注意要带返回值，因为head在函数体内部被改变了。
//而函数体内部的改变，在函数外面是透明的
List reverseWithOutHead(List head)
{
	if(head==NULL || head->next==NULL)
		return head;
	List p = head;
	List q = head->next;
	while(q)
	{
		p->next = q->next;
		q->next = head;
		head = q;
		q = p->next;
	}
	return head;
}
int main()
{
	int N = 6;
	//带头结点的操作
	/*List head = createListWithHead(N);
	traverseWithHead(head);
	reverseWithHead(head);
	traverseWithHead(head);
	*/
	//不带头结点的操作
	List head = createListWithOutHead(N);
	traverseWithOutHead(head);
	head = reverseWithOutHead(head);
	traverseWithOutHead(head);
	getchar();
	return 0;
}