已知head指向一个带头结点的单词链表,链表中每个结点包含数据long和指向被解构结点的指针

#include 
#include 
#include 

#define elemType long /*元素类型*/
#define elemPrintType "%ld\t" /*元素打印类型*/
#define status int
#define OVERFLOW -1
#define ERROR 0
#define OK 1

/* 单链表数据结构 */
typedef struct lNode {
	elemType data;
	struct lNode *next;
} lNode, *linkList;

/******************************** 以下为函数声明 ********************************/
void initList (linkList *L);							/* 初始化 */
void destroyList (linkList L);							/* 销毁 */
status listIsEmpty (linkList L);						/* 判断单链表是否为空 */
int listLength (linkList L);							/* 获取单链表长度 */
status listInsertNode (linkList L, int i, elemType e);	/* 单链表指定位置插入新元素 */
status listPrint (linkList L);							/* 输出链表 */
status listReverse (linkList L);						/* 逆置链表 */
/******************************** 以上为函数声明 ********************************/

/* 初始化 */
/* 操作结果：构造一个空的单链表L */
void initList (linkList *L) {
	*L = (linkList) malloc (sizeof (struct lNode)); /* 产生头节点，并使L指向此头节点 */
	if(!*L) /* 内存分配失败 */
		exit (OVERFLOW);
	(*L)->next = NULL; /* 指针域为空 */
}

/* 销毁 */
/* 初始条件：单链表L已存在。操作结果：销毁单链表L */
void destroyList (linkList L) {
	linkList p,q;
	
	p = L->next; /* p指向第一个结点 */
	while (p) { /* 没到表尾 */
		q = p->next;
    	free (p);
    	p = q;
	}
	free (L);
}

/* 判断单链表是否为空 */
/* 初始条件：单链表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE */
status listIsEmpty (linkList L) {
	return L->next == NULL;
}

/* 获取单链表长度 */
/* 初始条件：单链表L已存在。操作结果：返回L中数据元素个数 */
int listLength (linkList L) {
	int i = 0;
	linkList p = L->next; /* p指向第一个结点 */
	
	while (p) { /* 没到表尾 */
    	i++;
    	p=p->next;
	}
	
	return i;
}

/* 单链表指定位置插入新元素 */
/* 操作结果：在带头结点的单链表L中第i个位置之前插入元素e */
status listInsertNode (linkList L, int i, elemType e) {
	int j=0;
	linkList p=L,s;
	
	while (p && j		p = p->next;
    	j++;
	}
	
	if (!p || j>i-1) /* 插入位置不合理：i小于1或者大于表长 */
		return ERROR;

	/* 生成新结点，并插入L中 */
	s = (linkList) malloc (sizeof (struct lNode));
	s->data = e;
	s->next = p->next;
	p->next = s;
	
	return OK;
}

/* 输出链表 */
status listPrint (linkList L) {
	if (listIsEmpty (L)) {
		puts ("链表为空！");
		return OK;
	}
	linkList p = L->next; /* p指向第一个结点 */
	while (p!=NULL) {
		printf (elemPrintType,p->data);
		p = p->next;
	}
	putchar ('\n');
	return OK;
}

/* 逆置链表 */
/* 初始条件：单链表L已存在。操作结果：链表元素逆置 */
status listReverse (linkList L) {
	linkList p, q;
	
	if (listIsEmpty (L)||listLength (L)==1) /* 若L为空表或只有一个元素 */ 
        return ERROR;  
	
	p = L->next->next; /* p指向第2个结点 */
	L->next->next = NULL; /* 首结点置为尾结点 */
	
	/* 自第2个结点起遍历链表，循环将当前结点插入到头结点之后以逆置链表 */
    while (p) {
        q = p->next; /* q指向p的后继结点 */ 
		/* 将p插入到头结点之后 */
		p->next = L->next;
		L->next=p;
		/* 访问下一结点 */
		p = q;
    }
    return OK;
}

int main (void) {
	linkList head;
	elemType a=1,b=2,c=3,d=4;
	
	/* 初始化链表 */
	initList (&head);
	/* 插入若干元素 */
	listInsertNode (head, 1, a);
	listInsertNode (head, 1, b);
	listInsertNode (head, 1, c);
	listInsertNode (head, 1, d);
	
	puts ("原链表内容：");
	listPrint (head); /* 逆置链表 */
	
	listReverse (head); /* 逆置链表 */
	puts ("逆置后链表内容：");
	listPrint (head);
	
	destroyList (head); /* 销毁 */
	
	getch ();
	return 0 ;
}

运行结果

node* reverse(node * head) //如果不带返回值,参数要写成node ** head ,涉及到参数值传递和地址传递问题
{
node *tmp=NULL; //临时保存翻转后的链表
node *ptr=NULL; //指向剩下的没有翻转的链表
if(head == NULL)
return head;

tmp = head ; //处理链表末尾使之指向NULL
head=head->next;
if(tmp !=NULL)
{
tmp->next = NULL; //末尾
}
else
{
return head; //只有一个节点
}

while(head != NULL) //思想是从待翻转的链表中依次取一个节点，每次取一个都放在临时保存的链表的最前面
{
ptr = head->next; //保存head节点后面的节点的指针
head->next = tmp; //将head节点放在临时链表最前面
tmp = head; //临时链表头节点更新为head
head = ptr;
}
head = tmp;
return head;
}

以上是最好的方法，还有一种就是先遍历链表，把每个节点的指针存储在一个数组中，然后从数组最后开始，反过来重新构建链表，这样空间复杂度高,但是简单