C语言数据结构 链表与归并排序实例详解

Node* sort (Node* beg)

{

  if(beg==tail || beg->next==tail)returnbeg;

  Node* a = beg; Node* b = beg->next;

  while(b!=tail && b->next != tail)

  {

    a = a->next; b = b->next->next;

  }

  b = a->next; //the beginning of right part

  a->next = tail;//the end of left part

  returnmerge(sort(beg), sort(b));

}

Node* LinkedList::merge(Node* a, Node* b)

{

    Node dummy = Node();

    Node* head = &dummy;

    // temp是正在合并的表的节点

    Node* temp = head;

    while(a!=tail && b!=tail)//逐个比较链表a和链表b的每个元素

    {

        if(a->data <= b-="">data)

        {

            // 如果a比b小, 那么当前结点的后继就是a

            temp->next = a;

            // 把当前节点移向后继

            temp = a;

            // a后移

            a = a->next;

        }

        else

        {

            temp->next = b;

            temp = b;

            b = b->next;

        }

        // 如果原表a已经排完,那么新表后面就放b的剩余元素

        // 否则仍然以a为标准和b进行比较

        temp->next = (a==tail) ? b : a;

    }

    returnhead->next;

}