算法面试题

1、两个有序的数组求中位数（时间复杂度O（log(n+m））

http://blog.csdn.net/kenby/article/details/6833407（这个算法有一定的缺陷，仅做参考）

2、如何解决hash冲突

http://blog.sina.com.cn/s/blog_54f82cc20100zuuy.html

3、调整数组顺序使奇数位于偶数前面

void ReorderOddEven(int *pData, unsigned int length) { if(pData == NULL || length = 0) return; int *pBegin = pData; int *pEnd = pData + length - 1; while(pBegin < pEnd){ //若是奇数向后移动 while(pBegin < pEnd && (*pBegin & 1) != 0) pBegin ++; //若是偶数向前移动 while(pBegin < pEnd && (*pEnd & 1) == 0) pEnd --; //交换位置 if(pBegin < pEnd) { int temp = *pBegin; *pBegin = *pEnd; *pEnd = temp; } } } 4、链表中倒数第k个节点

ListNode *FindKthTotail(ListNode *pListHead, unsigned int k) { if(pListHead == NULL || k == 0) //判断是否合法 return NULL; ListNode *pAhead = pListHead; ListNode *pBehand = NULL; for(int i = 0;i < k - 1;i ++){//遍历到第k个数 if(pAhead->next == NULL) return NULL; pAhead = pAhead->next; } pBehand = pListHead; while(pAhead->next != NULL)//新增一个指针从头开始 { pAhead = pAhead->next; pBehand = pBehand->next; } return pBehand; }

5、链表的反转（倒插法）

ListNode *ReverseList(ListNode *pHead){ ListNode *pNode = pHead; ListNode *pPrev = NULL; while(pNode != NULL){ ListNode *pNext = pNode->next; pNode->next = pPrev; pPrev = pNode; pNode = pNext; } return pPrev; }

7、合并两个排序的链表

ListNode *Merge(ListNode *pHead1, ListNode *pHead2) { if(pHead1 == NULL) return pHead2; else if(pHead2 == NULL) return pHead1; ListNode *pMergeHead = NULL; if(pHead1->value < pHead2->value){ pMergeHead = pHead1; pMergeHead->next = Merge(pHead1->next,pHead2); } else{ pMergeHead = pHead2; pMergeHead->next = Merge(pHead1,pHead2->next); } return pMergeHead; }