链表的排序，好的做法是交换指针域。链表节点的数据域可能比较大，交换数据域可能会涉及拷贝过多的内存，影响性能。链表是链式存储，无法随机访问(base_addr + offset), 所以比较适合的办法是用比较两两相邻节点的冒泡排序法。当然还有一个办法就是，把所有的链表地址存到一个数组里，排序后重新遍历设置所有指针域，这个就多了两次遍历，也可以。下面是交换指针域的一个单链表冒泡排序的例子：
#include <stdio.h> #include <stdlib.h> struct Node { int data; struct Node *next; }; struct Node *listHead = NULL; struct Node *listTail = NULL; /* 交换指针域，冒泡排序单链表 */ void sortList() { struct Node *cur, *prev, *tmp, *last; cur = listHead; prev = listHead; last = NULL; int i = 0, j = 0; while (cur != last) { i = 0; while (cur != NULL && cur->next != last) { if (cur->data > cur->next->data) { /* cur, cur->next 交换位置 */ tmp = cur->next; cur->next = cur->next->next; tmp->next = cur; if (i > 0) prev->next = tmp; /* 第一次交换: prev == cur */ /* 移动 prev, cur 节点，这里cur已经是下一个 */ prev = tmp; /* 维护头结点 */ if (i == 0) listHead = prev; } else { /* 节点不交换位置 */ prev = cur; cur = cur->next; } i++; } /* 维护尾节点 */ if (j++ == 0) { listTail = cur; listTail->next = NULL; } last = cur; cur = listHead; prev = listHead; } } void initList() { size_t i; struct Node *node; int nums[] = {8, 7, 6, 5, 0, 2, 3, 9, 4, 1}; for (i = 0; i < sizeof(nums) / sizeof(int); i++) { node = (struct Node*)malloc(sizeof(struct Node)); node->data = nums[i]; node->next = NULL; if (listHead == NULL) { listHead = node; } if (listTail == NULL) { listTail = node; } else { listTail->next = node; listTail = node; } } } void printList() { struct Node *node; node = listHead; while (node != NULL) { printf("%d ", node->data); node = node->next; } printf("\n"); } int main() { initList(); printf("before: "); printList(); sortList(); printf("after : "); printList(); printf("head %d, tail %d\n", listHead->data, listTail->data); return 0; }