今天上午自己写了一个链表的反转

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

typedef struct _node
{
	int n;
	_node *next;
} node;

int create_link(node **phead)
{
	int x = 0;
	printf("input nums, press Ctrl+Z(win) or Ctrl+D(linux) to endn");
	if (scanf("%d", &x) <= 0)
	{
		return 0;
	}
	*phead = (node *)malloc(sizeof(node));
	if ( ! *phead)
	{
		return 1;
	}
	(*phead)->n = x;
	(*phead)->next = NULL;
	node *now = *phead;
	while (scanf("%d", &x) == 1)
	{
		node *new_node = (node *)malloc(sizeof(node));
		if ( ! new_node)
		{
			// TO-DO: free memory
			return 1;
		}
		new_node->n = x;
		new_node->next = NULL;
		now->next = new_node;
		now = new_node;
	}
	return 0;
}

void print_link(node *head)
{
	node *now = head;
	while (now)
	{
		printf("%d", now->n);
		if (now->next)
		{
			printf(" -> ");
		}
		now = now->next;
	}
	printf("n");
}

void delete_link(node **head)
{
	node *now = *head;
	while (now)
	{
		node *tmp = now->next;
		free(now);
		now = tmp;
	}
	*head = NULL;
}

void reverse_link(node **phead)
{
	node *pre = *phead;
	node *curr = pre->next;
	if ( ! curr)
	{
		// 只有一个节点
		return;
	}
	node *next = curr->next;
	pre->next = NULL;
	while (1)
	{
		curr->next = pre;
		if (next)
		{
			pre = curr;
			curr = next;
			next = next->next;
		}
		else
		{
			break;
		}
	}
	*phead = curr;
}

int main()
{
	node *head = NULL;
	create_link(&head);
	print_link(head);
	reverse_link(&head);
	print_link(head);
	delete_link(&head);
	return 0;
}

输入输出

input nums, press Ctrl+Z(win) or Ctrl+D(linux) to end
3 1 2 4 0
^Z
3 -> 1 -> 2 -> 4 -> 0
0 -> 4 -> 2 -> 1 -> 3

==================================================

2012-09-08 12:39:03 update 参考这里 http://blog.csdn.net/rerli/art…，反转函数有更简单的写法

void reverse_link(node **phead)
{
	node *pre = NULL;
	node *curr = *phead;
	node *next = NULL;
	while (curr)
	{
		next = curr->next;
		curr->next = pre;
		pre = curr;
		curr = next;
	}
	*phead = pre;
}

================================================

参考这里，http://blog.csdn.net/rerli/art…，写了链表的插入排序

void insert_sort(node **phead)
{
	node *head = *phead;
	// 把 head 的下一节点保存起来
	node *first = head->next;
	// 断开 head，使其成为初始的有序链表
	head->next = NULL;
	while (first)
	{
		node *p, *q, *t;
		// 找到插入点
		for (t=first, q=head; q && q->n < t->n; p=q, q=q->next);
		// 把 first 节点从无序链表中断开
		first = first->next;

		if (q == head)
		{
			// 插入在头结点之前
			head = t;
		}
		else
		{
			// p 是 q 的前驱
			p->next = t;
		}
		t->next = q;
	}
	*phead = head;
}

======================================================

2012-09-08 15:02:07 update 相比于传二维指针，可以使用 c++ 的写法，传引用，这样可读性会高很多

int create_link(node *&head)
{
	int x = 0;
	printf("input nums, press Ctrl+Z(win) or Ctrl+D(linux) to endn");
	if (scanf("%d", &x) <= 0)
	{
		return 0;
	}
	head = (node *)malloc(sizeof(node));
	if ( ! head)
	{
		return 1;
	}
	head->n = x;
	head->next = NULL;
	node *now = head;
	while (scanf("%d", &x) == 1)
	{
		node *new_node = (node *)malloc(sizeof(node));
		if ( ! new_node)
		{
			// TO-DO: free memory
			return 1;
		}
		new_node->n = x;
		new_node->next = NULL;
		now->next = new_node;
		now = new_node;
	}
	return 0;
}

调用的时候改成

int main()
{
	node *head = NULL;
	create_link(head);
	print_link(head);
	reverse_link(&head);
	print_link(head);
	insert_sort(&head);
	print_link(head);
	delete_link(&head);
	return 0;
}