谷歌的电话面试都是用Google Doc敲代码,题目本身不是很难,不过想敲出bug-free还是很难的。
直接上题目
A. 链表重组
有一个链表,里面用int 存放key,现在给定一个值 val,我们重组链表,小于val的节点放在前面。并且相对顺序不能变化
- struct TreeNode{
- int value;
- TreeNode *pNext;
- };
- int ReconstructLinkedListByValue(TreeNode *head, int val){
- TreeNode *leftPart = NULL, *leftHead = NULL;
- TreeNode *rightPart = NULL, *rightHead = NULL;
- while(head){
- if(head->value > val){
- if(leftPart == NULL) leftHead = leftPart = head;
- else{
- leftPart->pNext = head;
- leftPart = head;
- }
- }
- else{
- if(rightPart == NULL) rightHead = rightPart= head;
- else{
- rightPart->pNext = head;
- rightPart= head;
- }
- }
- head = head->pNext;
- }
- if(leftHead == NULL){
- return rightHead;
- }
- else{
- leftPart.pNext = rightHead;
- return leftHead;
- }
- }