翻转单向列表

#include <stdio.h>
#include <stdlib.h>

struct Node {
	int value;
	struct Node *next;
};

struct List {
	struct Node *First;
	struct Node *Last;
};

struct List *list_create()
{	
	struct List *list = (struct List *)malloc(sizeof(struct List));
	list->First = NULL;
	list->Last = NULL;
	
	return list;
}

void list_free(struct List *list)
{
	if (list == NULL || list->First == NULL) {
		return;
	}
	
	struct Node *p = NULL;
	
	do {
		p = list->First->next;
		printf("free %d\n", list->First->value);
		free(list->First);
		list->First = p;	
	} while (p != NULL);
	
	free(list);
}

void list_append(struct List *list, int value)
{
	struct Node *node = (struct Node *)malloc(sizeof(struct Node));
	node->value = value;
	node->next = NULL;
		
	if (list->First == NULL) {
		list->First = node;
	} 
	else {
		list->Last->next = node;	
	}
        list->Last = node;
}

void list_print(struct List *list) 
{
	struct Node *p = list->First;
	while (p != NULL) {
		printf("%d\n", p->value);
		p = p->next;
	}
}

void list_reverse(struct List *list) 
{
	if (list == NULL || list->First == NULL || list->First->next == NULL) {
		return;
	}
	
	struct Node *p = list->First;
	struct Node *q = list->First->next;
	struct Node *n = q->next;
	list->Last = list->First;
	
	while (1) {
		q->next = p;
		
		if (n == NULL) {
			list->First = q;
			break;
		}
		
		p = q;
		q = n;
		n = q->next;
	}
	
	list->Last->next = NULL;
}

void list_reverse_two_node(struct List *list, struct Node *first, struct Node *second)
{
	if (second == NULL) {
		list->First = first;
		return;
	}
	
	struct Node *third = second->next;
	second->next = first;
	
	list_reverse_two_node(list, second, third);
}

void list_reverse2(struct List *list)
{
	if (list == NULL || list->First == NULL || list->First->next == NULL) {
		return;
	}
	
	list->Last = list->First;
	list_reverse_two_node(list, list->First, list->First->next);
	list->Last->next = NULL;
}

int main(int argc, char *argv[]) {
	struct List *list = list_create();
	
	list_append(list, 1);
	list_append(list, 2);
	list_append(list, 3);
	list_append(list, 4);
	list_append(list, 5);
	list_append(list, 6);
	
	list_print(list);
	puts("---------------------------");
	
	list_reverse(list);
	list_print(list);
	puts("---------------------------");
	
	list_reverse(list);
	list_print(list);
	puts("---------------------------");
	
	list_free(list);
	
	return 0;
}

输出结果:

1
2
3
4
5
6

---------------------------

6
5
4
3
2
1

---------------------------

1
2
3
4
5
6

---------------------------

free 1
free 2
free 3
free 4
free 5
free 6
Written on 2016-02-26