笔试算法题（17）：奇偶数分置数组前后段 & 反序访问链表

出题：输入一个数组，要求通过交换操作将奇数索引的元素调整到数组前半部分，偶数索引的元素调整到数组后半部分；

分析：

当然如果没有额外要求的话很容易实现，最好使用In-Place的实现策略；考虑插入排序的策略，不过这里的判断条件是遇到第一个奇数的时候才停止。时间复杂度为O（N^2）；
另外可以使用快速排序策略，使用两个指针进行双向扫描，左指针一旦遇到偶数则停止，右指针一旦遇到奇数则停止，然后交换左右指针索引的元素，知道左右指针交叉。时间复杂度为O（N）。如果题目要求在一个序列中按照某标准将序列划分成几个部分，快速排序的思路都可以使用；
快速排序的思路可用于多种问题，只要是需要按照某种标准将一个序列划分成两个或者更多的部分，都可以使用快速排序的策略

解题：

 1 /**
 2  * 从数组第三项开始，假设左边的数组都已经是奇数项在前，偶数项在后
 3  * 然后将当前索引项插入已经排好序的左序列中，一旦遇到奇数项则插入到
 4  * 其右边的偶数项，其他项顺次往右移，跟插入排序类似
 5  * 遍历数组的时候跳过偶数项，可以加速排序时间
 6  * */
 7 void OddEvenInsert(int *array, int length) {
 8         int j, temp;
 9         if(length <= 2) return;
10         for(int i=2; i<length;i+=2) {
11                 temp=array[i];
12                 j=i-1;
13                 while(true) {
14                         if(array[j] %2 == 0) {
15                                 array[j+1]=array[j];
16                                 j--;
17                         } else {
18                                 break;
19                         }
20                 }
21                 array[j+1]=temp;
22         }
23 }
24 
25 void OddEvenQuick(int *array, int i, int j) {
26         int *left=array+i;
27         int *right=array+j;
28 
29         int temp;
30         while(true) {
31                 while(*left%2 != 0) left++;
32                 while(*right%2 != 1) right--;
33                 if(left>right) break;
34 
35                 temp=*left;
36                 *left=*right;
37                 *right=temp;
38 
39                 left++;
40                 right--;
41         }
42 }
43 
44 int main() {
45         int array[]={1,2,3,4,5,6,7,8,9};
46         OddEvenInsert(array, 9);
47         for(int i=0;i<9;i++) {
48                 printf("%d, ",array[i]);
49         }
50         return 0;
51 }

出题：输入一个链表的头结点，要求反序输出每个结点的值

分析：典型的递归实现，系统栈结构是为程序员免费提供的最好的数据结构

解题：

 1 struct Node {
 2         int v;
 3         Node *next;
 4 };
 5 
 6 void reversePrint(Node *current) {
 7         if(current->next != NULL)
 8                 reversePrint(current->next);
 9         printf("%d, ",current->v);
10 }
11 
12 int main() {
13         Node* a1=new Node(); a1->v=2;
14                 Node* a2=new Node(); a2->v=4;a1->next=a2;
15                 Node* a3=new Node(); a3->v=6;a2->next=a3;
16                 Node* a4=new Node(); a4->v=8;a3->next=a4;
17                 Node* a5=new Node(); a5->v=10;a4->next=a5;
18                 Node* a6=new Node(); a6->v=11;a5->next=a6; a6->next=NULL;
19         reversePrint(a1);
20         return 0;
21 }