合并有序链表

问题描述：合并两个有序链表，不使用额外空间

思路：由于链表已经有序，只需要设置两个工作指针，每次把较小的那个指针附加在目标链表后面。

LinkList mergeSortedList(LinkList head1, LinkList head2)
{
// 这里略过链表为空的情况
  LinkNode* p1 = head->next;
  LinkNode* p2 = head->next;
  LinkNode* p = NULL;
  head1->next = p;
  if(p1->data <= p2->data)
  {
    p=p1;
    p1=p1->next;
  }
  if(p2->data > p2->data)
   {
    p=p2;
    p2=p2->next;
  }
  while(p1 && p2)
  {
    if(p1->data <= p2->data)
    {
            p->next = p1;
            p = p->next;
            p1 = p->next;
     }
    if(p1->data < p2->data)
    {
        p->next = p2;
        p = p->next;
        p2=p2->next;
    }
  }
if(p2) p1=p2;
p->next = p1; //剩下的直接接到后面
return head;
}