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

Node* sort (Node* beg)
{
  if(beg==tail || beg->next==tail) return beg;
  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
  return merge(sort(beg), sort(b));
}

Node* LinkedList<T>::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;
	}
	return head->next;
}