首页 > 代码库 > 链表的归并排序
链表的归并排序
因为链表是节点式存储,不能做到随机存储,但是对于两个有序链表之间的合并不需要额外的空间,在O(1)空间复杂度O(n)时间复杂度内即可完成。所以对于链表排序,使用归并排序比较划算。
typedef struct Node List; struct Node { int value; List* next; };
//链表节点结构体
首先合并两个有序的链表:
/* 在合并的时候始终保持一个链表的节点插入另一个链表中 这里始终保证first是最终的链表,将second链表中的每一个节点逐步插入到first中 */ List* Merge(List* first,List* second) { List* head = NULL; List* current = NULL; if(first == NULL) return second; if(second == NULL) return first; if(first->value > second->value) { current = first; first = second; second = current; } head = first; current = first; first = first->next; //始终将second的节点插入到first链表中 while( first != NULL && second != NULL) { List* temp = NULL; if(first->value > second->value) { temp = second->next; current->next = second; second->next = first; current = second; second = temp; } else { current = first; first = first->next; } } if(first == NULL) current->next = second; return head; }
上面的代码是合并两个有序的链表,始终将second的链表节点插入到first链表节点,所以second始终指向头节点。对于first节点,始终将被插入的节点插入到current节点的后面,如果对于second节点来说在first中没有找到合适的节点,那么就需要更新current和first节点位置。
链表归并排序的主要框架代码:
int List_length(List* list) { int len=0; List* temp = NULL; temp= list; while(temp != NULL) { len++; temp = temp->next; } return len; } List* MergeSort(List* list,int size) { if(size == 0 || size == 1) return list; List* middle = list; int i; for(i=1;i<size/2;i++) middle = middle->next; List* temp = middle->next; middle->next = NULL; middle = temp; List* left = MergeSort(list,i); List* right = MergeSort(middle,size-i); return Merge(right ,left); }
链表的归并排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。