面试题63：链表题，一个链表的节点结构

    struct Node { int data； Node*next； }； typedef struct Node Node；

    问：（1）已知链表的头节点head，写一个函数把这个链表逆序。（Intel公司题目）

    答：编写的程序如下所示。

    01　NodeReverseList（Nodehead）//链表逆序 02　{ 03　if（head==NULL||head-＞next==NULL） 04　return head； 05　Node*p1=head； 06　Node*p2=p1-＞next； 07　Node*p3=p2-＞next； 08　p1-＞next=NULL； 09　while（p3！=NULL） 10　{ 11　p2-＞next=p1； 12　p1=p2； 13　p2=p3； 14　p3=p3-＞next； 15　} 16　p2-＞next=p1； 17　head=p2； 18　return head； 19　}问：（2）已知两个链表head1和head2各自有序，请把它们合并成一个链表依然有序。（保留所有节点，即便大小相同）。（微软公司题目）答：编写的程序如下所示。 01　NodeMerge（Nodehead1，Node*head2） 02　{ 03　if（head1==NULL） 04　return head2； 05　if（head2==NULL） 06　return head1； 07　Node*head=NULL； 08　Node*p1=NULL； 09　Node*p2=NULL； 10　if（head1-＞data＜head2-＞data） 11　{ 12　head=head1； 13　p1=head1-＞next； 14　p2=head2； 15　} 16　else 17　{ 18　head=head2； 19　p2=head2-＞next； 20　p1=head1； 21　} 22　Node*pcurrent=head； 23　while（p1！=NULL＆＆p2！=NULL） 24　{ 25　if（p1-＞data＜=p2-＞data） 26　{ 27　pcurrent-＞next=p1； 28　pcurrent=p1； 29　p1=p1-＞next； 30　} 31　else 32　{ 33　pcurrent-＞next=p2； 34　pcurrent=p2； 35　p2=p2-＞next； 36　} 37　} 38　if（p1！=NULL） 39　pcurrent-＞next=p1； 40　if（p2！=NULL） 41　pcurrent-＞next=p2； 42　return head； 43　}问：（3）已知两个链表head1和head2各自有序，请把它们合并成一个链表依然有序，这次要求用递归方法进行。（Autodesk公司题目）答：编写的程序如下所示。 44　NodeMergeRecursive（Nodehead1，Node*head2） 45　{ 46　if（head1==NULL） 47　return head2； 48　if（head2==NULL） 49　return head1； 50　Node*head=NULL； 51　if（head1-＞data＜head2-＞data） 52　{ 53　head=head1； 54　head-＞next=MergeRecursive（head1-＞next,head2）； 55　} 56　else 57　{ 58　head=head2； 59　head-＞next=MergeRecursive（head1，head2-＞next）； 60　} 61　return head； 62　}