Google電話面試題目

谷歌的電話面試都是用Google Doc敲代碼，題目本身不是很難，不過想敲出bug-free還是很難的。

直接上題目

A. 鏈表重組

有一個鏈表，裡面用int 存放key，現在給定一個值 val，我們重組鏈表，小於val的節點放在前面。並且相對順序不能變化

1. struct TreeNode{ 
2.     int value; 
3.     TreeNode *pNext; 
4. }; 
5.  
6. int ReconstructLinkedListByValue(TreeNode *head, int val){ 
7.     TreeNode *leftPart = NULL, *leftHead = NULL; 
8.     TreeNode *rightPart = NULL, *rightHead = NULL; 
9.      
10.     while(head){ 
11.         if(head->value > val){ 
12.             if(leftPart == NULL) leftHead = leftPart = head; 
13.             else{ 
14.                 leftPart->pNext = head; 
15.                 leftPart = head; 
16.             } 
17. } 
18.         else{ 
19.             if(rightPart == NULL) rightHead = rightPart= head; 
20.             else{ 
21.                 rightPart->pNext = head; 
22.                 rightPart= head; 
23.             } 
24.         } 
25.         head = head->pNext; 
26.     } 
27.     if(leftHead  == NULL){ 
28.         return rightHead; 
29.     } 
30.     else{ 
31.         leftPart.pNext = rightHead; 
32.         return leftHead; 
33.     } 
34. }