Google電話面試題目

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

直接上題目

A. 鏈表重組

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

1. struct TreeNode{
2. int value;
3. TreeNode *pNext;
4. };
6. int ReconstructLinkedListByValue(TreeNode *head, int val){
7. TreeNode *leftPart = NULL, *leftHead = NULL;
8. TreeNode *rightPart = NULL, *rightHead = NULL;
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. }