链表逆序以及合并（非递归和递归）

/*

 * Description:

 *          链表逆序以及合并，非递归和递归实现。

 * Author  :FinL

 * Language: C

 * Date    : 2010-08-06

 */

#include

#include

struct Node{

int data;

Node *next;

};

typedef struct Node Node;

//已知链表的头结点，将链表逆序

Node *ReverseList(Node *head)

{

Node *p1,*p2,*p3;

if(NULL==head->next||NULL==head)

return head;

p1=head;

p2=p1->next;

p3=p2->next;

p1->next=NULL;

while(NULL!=p3)

{

p2->next=p1;

p1=p2;

p2=p3;

p3=p3->next;

}

p2->next=p1;

head=p2;

return head;

}

//合并两个各自有序的链表head1,head2为一个依然有序的链表(要求保留所有结点)。

Node *MergeList(Node *head1,Node *head2)

{

Node *p1,*p2,*head,*tmp;

if(NULL==head1)

return head2;

if(NULL==head2)

return head1;

if(head1->datadata)

{

head=head1;