链表排序

    二路归并（暂未实现）

    基本思想：维护一个队列，从头便利链表，找到一段按降序排列的链表段，一段一段的分开，然后将它们按顺序入队，每次从对头取出两个进行归并，归并后的结果入队。

 

#include 
        
          using namespace std; struct node{
      int d;     node *next;     node(int x){d = x;next = NULL;} }; //链表找中点 node *findminnode(node *head) {
      if(head == NULL || head->next == NULL) return head;     node *onestep = head;     node *twostep = head; while(twostep->next != NULL && twostep->next->next != NULL){
              onestep = onestep->next;         twostep = twostep->next->next;     } return onestep; } //两条单链表判断是否相交 bool judgexiangjiao(node *head1,node *head2) {
      if(head1 == NULL || head2 == NULL) return 0;     node *p1 = head1;     node *p2 = head2; while(p1->next != NULL) p1 = p1->next; while(p2->next != NULL) p2 = p2->next; if(p1 == p2) return 1; return 0; } //单链表判断有无环，并输出环的起始点 bool ishascycle(node *head,node *&onenode) {
      if(head == NULL || head->next== NULL) return 0;     node *onestep = head;     node *twostep = head; while(twostep->next != NULL && twostep->next->next != NULL){
              onestep = onestep->next;         twostep = twostep->next->next; if(onestep == twostep){
                  onenode = onestep; return 1;         }     } return 0; } node * findfirstnode(node *head) {
          node *onenode = NULL; bool isc = ishascycle(head,onenode); if(isc){
              node * fromhead = head;         node * fromonenode = onenode->next; int headcount = 0; int onecount = 0; while(fromhead != onenode){
                  fromhead=fromhead->next;             headcount++;         } while(fromonenode != onenode){
                  fromonenode = fromonenode->next;             onecount++;         } int cha = 0;         node *fromlong = NULL;         node *fromshort = NULL; if(headcount > onecount){
                  cha = headcount - onecount;             fromlong = head;             fromshort = onenode->next;         }else{
                  cha = onecount - headcount;             fromshort = head;             fromlong = onenode->next;         } while(cha--){
                  fromlong = fromlong->next;         } while(fromlong != fromshort){
                  fromshort = fromshort->next;             fromlong = fromlong->next;         } return fromlong;     } return NULL; } //链表逆序 node *reve(node *head) {
      if(head == NULL ||head->next == NULL) return NULL;     node *pre = NULL;     node *cur = head;     node *nex ; while(cur != NULL)     {
              nex = cur->next;         cur->next = pre;         pre = cur;         cur = nex;     } return pre; } int main() {
          node *head = new node(1);     node *n2 = new node(2);     node *n3 = new node(3);     node *n4 = new node(4);     node *n5 = new node(5);     node *n6 = new node(6);     node *n7 = new node(7);     node *n8 = new node(8);     head->next = n2;     n2->next = n3;     n3->next = n4;     n4->next = n5;     n5->next = n6;     n6->next = n7;     n7->next = n8;     cout<
         
          d<
          
           next = n3;     node * jiao ; bool an = ishascycle(head,jiao);     cout<
           
            <
            
             d<
             
              next = NULL; node *p = reve(head); while(p){ cout<
              
               d<<" "; p= p->next; } cout<