Cacher is the code snippet organizer for pro developers

typedef struct LNode
{
  int data;
  struct LNode *next;
}LNode , *LinkList;


// 对两个有序的链表进行递归的归并
LinkList MergeList_recursive(LinkList head1 , LinkList head2)
{
  LinkList result;
  if(head1 == NULL)
    return head2;
  if(head2 == NULL)
    return head1;
  if(head1->data < head2->data)
  {
    result = head1;
    result->next = MergeList_recursive(head1->next , head2);
  }
  else
  {
    result = head2;
    result->next = MergeList_recursive(head1 , head2->next);
  }
  return result;
}


// 对两个有序的链表进行非递归的归并
LinkList MergeList(LinkList head1 , LinkList head2)
{
  LinkList head , result = NULL;
  if(head1 == NULL)
    return head2;
  if(head2 == NULL)
    return head1;
  while(head1 && head2)
  {
    if(head1->data < head2->data)
    {
      if(result == NULL)
      {
        head = result = head1;
        head1 = head1->next;
      }else{
        result->next = head1;
        result = head1;
        head1 = head1->next;
      }
    }
    else
    {
      if(result == NULL)
      {
        head = result = head2;
        head2 = head2->next;
      }
      else
      {
        result->next = head2;
        result = head2;
        head2 = head2->next;
      }
    }
  }
  if(head1)
    result->next = head1;
  if(head2)
    result->next = head2;
  return head;
}

// 归并排序，参数为要排序的链表的头结点，函数返回值为排序后的链表的头结点
LinkList MergeSort(LinkList head)
{
  if(head == NULL)
    return NULL;
  LinkList r_head , slow , fast;
  r_head = slow = fast = head;


  // 找链表中间节点的两种方法
  /*
  while(fast->next != NULL)
  {
    if(fast->next->next != NULL)
    {
    slow = slow->next;
    fast = fast->next->next;
    }
    else
      fast = fast->next;
  }*/


  while(fast->next != NULL && fast->next->next != NULL)
  {
    slow = slow->next;
    fast = fast->next->next;
  }

  if(slow->next == NULL)    // 链表中只有一个节点
    return r_head;
  fast = slow->next;
  slow->next = NULL;
  slow = head;
  // 函数MergeList是对两个有序链表进行归并，返回值是归并后的链表的头结点
  //r_head = MergeList_recursive(MergeSort(slow) , MergeSort(fast));
  r_head = MergeList(MergeSort(slow) , MergeSort(fast));
  return r_head;
}