程序员必看 c++笔试题汇总(1)(9)

40. 链表题：一个链表的结点结构

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

(1)已知链表的头结点head，写一个函数把这个链表逆序 ( Intel)

Node * ReverseList(Node *head) //链表逆序  
{  
if ( head == NULL || head->next == NULL )  
return head;  
Node *p1 = head ;  
Node *p2 = p1->next ;  
Node *p3 = p2->next ;  
p1->next = NULL ;  
while ( p3 != NULL )  
{  
p2->next = p1 ;  
p1 = p2 ;  
p2 = p3 ;  
p3 = p3->next ;  
}  
p2->next = p1 ;  
head = p2 ;  
return head ;  
}  

(2)已知两个链表head1 和head2 各自有序，请把它们合并成一个链表依然有序。(保留所有结点，即便大小相同)

Node * Merge(Node *head1 , Node *head2)  
{  
if ( head1 == NULL)  
return head2 ;  
if ( head2 == NULL)  
return head1 ;  
Node *head = NULL ;  
Node *p1 = NULL;  
Node *p2 = NULL;  
if ( head1->data < head2->data )  
{  
head = head1 ;  
p1 = head1->next;  
p2 = head2 ;  
}  
else 
{  
head = head2 ;  
p2 = head2->next ;  
p1 = head1 ;  
}  
Node *pcurrent = head ;  
while ( p1 != NULL && p2 != NULL)  
{  
if ( p1->data <= p2->data )  
{  
pcurrent->next = p1 ;  
pcurrent = p1 ;  
p1 = p1->next ;  
}  
else 
{  
pcurrent->next = p2 ;  
pcurrent = p2 ;  
p2 = p2->next ;  
}  
}  
if ( p1 != NULL )  
pcurrent->next = p1 ;  
if ( p2 != NULL )  
pcurrent->next = p2 ;  
return head ;  
}  

(3)已知两个链表head1 和head2 各自有序，请把它们合并成一个链表依然有序，这次要求用递归方法进行。 (Autodesk)

答案：

Node * MergeRecursive(Node *head1 , Node *head2)  
{  
if ( head1 == NULL )  
return head2 ;  
if ( head2 == NULL)  
return head1 ;  
Node *head = NULL ;  
if ( head1->data < head2->data )  
{  
head = head1 ;  
head->next = MergeRecursive(head1->next,head2);  
}  
else 
{  
head = head2 ;  
head->next = MergeRecursive(head1,head2->next);  
}  
return head ;  
}