reverse_list.c

将一个链表逆序

//链表逆序，一个是采取依次摘取节点的方式，另一个是递归方式
#include <stdio.h>
#include <stdlib.h>

typedef struct __node_t
{
	int value;
	struct __node_t *next;
}node_t, *pnode_t;
//typedef struct __node_t node_t;

int show (node_t *root)
{
	printf ("----------begin\n");
	node_t *p = root;
	while (p != NULL)
	{
		fprintf (stderr, "%d  ", p->value);
		p = p->next;
	}
	printf ("----------end\n");
	return 0;
}
int add (node_t **root, int value)
{
	node_t *tmp = *root;
	if (tmp == NULL)
	{
		node_t *p = (node_t *)malloc (sizeof (node_t));
		if (p == NULL)
		{
			printf ("%s.%d\n", __FILE__, __LINE__);
			exit (1);
		}
		p->value = value;
		p->next = NULL;
		*root = p;
		
		//show (*root);

		return 0;
	}
	while (tmp->next != NULL)
	{
		tmp = tmp->next;
	}
	node_t *p= (node_t *)malloc (sizeof (node_t));
	if (p == NULL)
	{
		printf ("%s.%d\n", __FILE__, __LINE__);
		
		exit (1);
	}
	p->value = value;
	p->next = NULL;
	tmp->next = p;
	
	//show(*root);

	return 0;
}
//链表逆序，采取依次摘取节点的方式
int reverse (node_t **root)
{
	if (*root == NULL)
		return 0;
	node_t *p1;
	node_t *new_root;
	
	p1 = (*root)->next;
	new_root = *root;
	new_root->next = NULL;
	*root = p1;
	
	while (*root != NULL)
	{
		//show (new_root);

		p1 = (*root)->next;
		(*root)->next = new_root;
		new_root = *root;

		*root = p1;
	}
	*root = new_root;

	return 0;
}
//链表逆序，递归方式
int rever2(node_t **root, node_t **tail)
{
	if (*root == NULL)
		return 0;
	if ((*root)->next == NULL)
	{
		*tail = *root;
		return 0;
	}
	node_t *old_root = *root;
	node_t *new_root = (*root)->next;
	node_t *new_tail = *tail;
	
	rever2 (&new_root, &new_tail);
	
	old_root->next = NULL;
	new_tail->next = old_root;
	new_tail = old_root;

	*root = new_root;
	*tail = new_tail;
	
	return 1;
}

int main (void)
{
	node_t *root = NULL;
	int i;
	for (i = 0; i < 3; i++)
	{
		add (&root, i);
		printf ("root= %p\n", root);
	}
	show(root);
	reverse (&root);
	show(root);

	node_t *tail = NULL;
	rever2 (&root, &tail);
	//rever2 (&root, NULL);
	show (root);

	return 0;
}