链表的合并与逆置

##单链表的合并与逆置
一.单链表合并
算法分析：
合并链表需要利用Merge函数，首先定义两个指针变量p和q,分别指向HA链表与HB链表的首元结点，并让r指向合并后的链表尾结点，合并后的链表头结点公用HA链表的头结点。
首先定义一下链表类型：

typedef struct node
{
char name[20];
int number;
int score;
struct node*next;
}Node,*linkList;    
合并程序如下：
Void Merge(linkList HA,linkList HB)
{
linkList HC;
Node *p,*q,*r;
p=HA->next;
q=HB->next;
r=HC=HA;
while(p&&q)
{
if(p->number<=q->next)
 { r->next=p;
  r=p;
  p=p->next;}
else
 { r->next=q;
   r=q;
   q=q->next;
 }
}
if(p) r->next=p;
if(q) r->next=q;
free(HB);

ok,以上就是单链表的合并。
接下来介绍一下单链表的逆置。
单链表的逆置有三种方法
（1） 头指针法：
算法分析：
依次取出原链表的每个节点，将其作为第一个节点插入到新链表中，逆置程序如下：

Void Reserve(linkList head)
{
  Node *p,*q;
  p=head->next;
  head->next=NULL;
  while(p)
  {
    q=p->next;
    p->next=head->next;
    head->next=p;
    p=q;
   }
 }      

(2)原地逆置：
每每修改两个相邻节点p,q的前后关系，增加一个t保存修改下一次的修改目标节点，留意一下，这个方法的时间复杂度为O(1)

Void Reserve(linkList head)
{ Node p=head->next;
  if(p==NULL||p->next=NULL)
    return head;
   Node q=p->next,t=q->next;
   while(q!=NULL)
   {
    q->next=p;
    p=q;
    q=t;
    if(t!=NULL)
     t=t->next;
    }
  head->next=NULL;
  head->next=p;
  return head;
 }

（3）递归逆置

Void Reserve(linkList head)
{
  if(head==NULL||head->next=NULL)
   return head;
  Node pre=Reverse(head->next)
  head->next->next=head;
  head->next=NULL;
  return head;
}   

好的，以上就到这里了。