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 ; }41. 分析一下这段程序的输出 (Autodesk)
class B { public: B() { cout<<"default constructor"<<endl; span="" <="">} ~B() { cout<<"destructed"<<endl; span="" <="">} B(int i):data(i) //B(int) works as a converter ( int -> instance of B) { cout<<"constructed by parameter " << data <<endl; span="" <="">} private: int data; }; B Play( B b) { return b ; } (1) results: int main(int argc, char* argv[]) constructed by parameter 5 { destructed B(5)形参析构 B t1 = Play(5); B t2 = Play(t1); destructed t1形参析构 return 0; destructed t2 注意顺序！ } destructed t1 (2) results: int main(int argc, char* argv[]) constructed by parameter 5 { destructed B(5)形参析构 B t1 = Play(5); B t2 = Play(10); constructed by parameter 10 return 0; destructed B(10)形参析构 } destructed t2 注意顺序！ destructed t142. 写一个函数找出一个整数数组中，第二大的数 (microsoft)
答案：
const int MINNUMBER = -32767 ; int find_sec_max( int data[] , int count) { int maxnumber = data[0] ; int sec_max = MINNUMBER ; for ( int i = 1 ; i < count ; i++) { if ( data[i] > maxnumber ) { sec_max = maxnumber ; maxnumber = data[i] ; } else { if ( data[i] > sec_max ) sec_max = data[i] ; } } return sec_max ; }43. 写一个在一个字符串(n)中寻找一个子串(m)第一个位置的函数。
KMP算法效率最好，时间复杂度是O(n+m)。
44. 多重继承的内存分配问题：比如有class A ： public class B， public class C {}那么A的内存结构大致是怎么样的?
这个是compiler-dependent的， 不同的实现其细节可能不同。
如果不考虑有虚函数、虚继承的话就相当简单;否则的话，相当复杂。
45. 如何判断一个单链表是有环的?(注意不能用标志位，最多只能用两个额外指针)
struct node { char val; node* next;}
bool check(const node* head) {} //return false ： 无环;true： 有环
一种O(n)的办法就是(搞两个指针，一个每次递增一步，一个每次递增两步，如果有环的话两者必然重合，反之亦然)：
bool check(const node* head) { if(head==NULL) return false; node *low=head, *fast=head->next; while(fast!=NULL && fast->next!=NULL) { low=low->next; fast=fast->next->next; if(low==fast) return true; } return false; }