Google电话面试题目

谷歌的电话面试都是用Google Doc敲代码，题目本身不是很难，不过想敲出bug-free还是很难的。

直接上题目

A. 链表重组

有一个链表，里面用int 存放key，现在给定一个值 val，我们重组链表，小于val的节点放在前面。并且相对顺序不能变化

1. struct TreeNode{      int value; 
2.     TreeNode *pNext;  }; 
3.   int ReconstructLinkedListByValue(TreeNode *head, int val){ 
4.     TreeNode *leftPart = NULL, *leftHead = NULL;      TreeNode *rightPart = NULL, *rightHead = NULL; 
5.           while(head){ 
6.         if(head->value > val){              if(leftPart == NULL) leftHead = leftPart = head; 
7.             else{                  leftPart->pNext = head; 
8.                 leftPart = head;              } 
9. }          else{ 
10.             if(rightPart == NULL) rightHead = rightPart= head;              else{ 
11.                 rightPart->pNext = head;                  rightPart= head; 
12.             }          } 
13.         head = head->pNext;      } 
14.     if(leftHead  == NULL){          return rightHead; 
15.     }      else{ 
16.         leftPart.pNext = rightHead;          return leftHead; 
17.     }  }