已知两个链表head1和head2各自有序，请把他们合并成一个链表依然有序
1 3 5 7，
2 4 6 8，
合并 1 2 3 4 5 6 7 8
代码实现如下
//思路：比较两个链表中data的值按小到大重新分到新的链表中 Node * Merge(Node *head1 , Node *head2) { if ( head1 == NULL) //如果head1为空表 return head2 ; if ( head2 == NULL) //head2为空 return head1 ; Node *head = NULL ; //保存data小的head的地址 Node *p1 = NULL; //保存data小的head的下一个指针 Node *p2 = NULL; //保存另一个head的指针 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) { //比较两个链表中data的值将小的data的表分到pcurrent上 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 ) //如果p2空将p1剩下的写入新链表的尾部 pcurrent->next = p1 ; if ( p2 != NULL ) //如果p1空将p2剩下的写入新链表的尾部 pcurrent->next = p2 ; return head ; }