一、关于指针的思考
指针的基本概念：
int a[100]; int *p; p=a;
以上代码有一些基本的等价，需要铭记。
p等价于&a[0]等价于a
*p等价于a[0]等价于*a
*(p+1)等价于p[1]等价于a[1]等价于*(a+1)
但是，如果对数组名取址呢？
int a[]={1,2,3};
int *p;
int **q;
p=a;
q=&a;
printf("%x\n",p);
printf("%x\n",q);
这时候会发生错误，
error C2440: '=' : cannot convert from 'int (*)[3]' to 'int **'
printf("sizeof(p)=%d\n",sizeof(p));
printf("sizeof(q)=%d\n",sizeof(q));
printf("sizeof(a)=%d\n",sizeof(a));
printf("%x\n",a);
printf("%x\n",&a);
我们加上着三句，看看三个指针占用的内存大小，发现是
大小分别是4，4，12。那就意味着，&a与&a+1的距离是3个int单位（12 bytes)。
同时可以看到，a与&a的地址是一样的。
所以我们可以知道，虽然对a取&了，但是并不是传统意义上取a值所在的内存地址。
同时我们要清楚，&a的数据类型是 int (*)[3]，占用12个bytes。
所以int **q; q=&a会报错。
怎么解决这个问题呢？将q的数据类型声明为int (*q)[3];
或者int *q; q=(int *)&a;
但是如果想用两重指针，是不能实现的。
二、金字塔路径和
这个是一家大外企，名声很大，招人很少，给的米很多。
我笔的是FPGA研发岗。问的是C语言问题。
这个是金字塔状结构，从顶部开始出发，沿着红色线出发，到达底部。
求路径和最小值。
（1）存储结构？
刚开始我想用二叉树。但是如果用二叉树，第5层就得用16个节点存储，会有大量的冗余。
其实，用数组就可以了。一个5x5的数组就搞定了。
（2）算法
如果允许修改数组内容，从上往下走一遍，每个节点从前两个节点中选择较小的一个相加就和，到底的时候，就会出现一排数值，选择就小的一个就是路径的最小和。
#include <stdio.h>
#include <stdlib.h>
void print(int (*p)[5],int N)
{
int i,j;
for(i=0;i<N;i++)
{
for(j=0;j<=i;j++)
{
printf(" %d",p[i][j]);
}
printf("\n");
}
}
void process(int (*a)[5],int N)
{
int i,j;
for(i=1;i<N;i++)
{
for(j=0;j<=i;j++)
{
if(j==0)
a[i][j]+=a[i-1][j];
else if(i==j)
a[i][j]+=a[i-1][j-1];
else if(a[i-1][j-1]>a[i-1][j])
a[i][j]+=a[i-1][j];
else
a[i][j]+=a[i-1][j-1];
}
}
printf("\n");
}
int main()
{
int a[5][5]={{1,},{3,2},{2,6,8},{6,7,4,2},{1,6,4,3,5}};
int i;
int min;
print(a,5);
process(a,5);
print(a,5);
for(i=1,min=a[4][0];i<5;i++)
if(a[4][i]<min)
min=a[4][i];
printf("the minimum number gained is %d\n",min);
}
三、链表翻转
一个单向链表，将其翻转。
比如1->2->3的结果，翻转就是3->2->1。
这个是一家台企和这个美国大公司共同问的一个问题，可见这题很普遍啊。
台企主要招去做手机底层驱动的软件开发，美企是做FPGA的。
node *init_link()
{
int i;
node *head,*p;
head=(node *)malloc(sizeof(node));
head->data=0;
p=head;
for(i=1;i<N;i++)
{
p=p->next;
p=(node *)malloc(sizeof(node));
p->data=i;
}
p->next=NULL;
return head;
}
谁能告诉，上面的这段单向链表的初始化出了什么问题？
这个是很多人容易犯的错误。下一个节点如果没有申请内存的话，将指针移到下一个节点，前节点是找不到的。
以下是我些的完全代码。
#include <stdio.h>
#include <stdlib.h>
#define N 10
typedef struct NODE{
int data;
struct NODE *next;
}node;
node *init_link()
{
int i;
node *head,*p;
head=(node *)malloc(sizeof(node));
head->data=0;
p=head;
for(i=1;i<N;i++)
{
p->next=(node *)malloc(sizeof(node));
p=p->next;
p->data=i;
}
p->next=NULL;
return head;
}
void print_link(node *head)
{
node *p;
p=head;
while(p!=NULL)
{
printf("%d ",p->data);
p=p->next;
}
printf("\n");
}
void reverse_link(node **head)
{
node *p;
node *front,*back;
p=*head;
front=NULL;
while(p!=NULL)
{
back=p->next;
p->next=front;
front=p;
p=back;
}
*head=front;
}
int main()
{
node *head;
head=init_link();
print_link(head);
reverse_link(&head);
print_link(head);
return 0;
}
上面代码里面的链表初始化长度N考试是不知道的，笔试者应该只需要写reverse_link这个函数。整个题的难度系数很小，记得传入reverse_link函数的时候对链表头节点取地址就OK了。因为一般菜鸟不会想到传地址，比如我。
四、查找单向链表中倒数某个节点的值
假设这里有个单向链表，长度不详。想找到倒数第m个节点。怎么办？
菜鸟上场喽。这题？简单！
（1）、扫链表一遍，复制到数组里，然后看倒数第m个节点。大爷你想找哪个节点找哪个！
做算法，一定要假设几个极端情况。如果这个链表很长很长，存着空空老师几十个G的电影，你就不会傻帽地想申请新内存了。
（2）、把单向链表为双向。
数据结构不许改。
（3）、扫两遍，第一遍知道链表长度N，第二遍找第N-m个元素。
大哥，这傻子都能想到的solution。因为同一，如果这个玩意儿很大，大部分放硬盘里，重复读两遍，需要很多IO操作。这个也是不能接受的。虽然时间复杂度都是O(n)。
（4）、构造一个FIFO，长度m。读一个节点，扔FIFO里面。当读完单向链表时，FIFO里面出来的就是需要的那个节点，如果FIFO里面没出来东西，说明单向链表长度不足m。
如果m=1000000000000000000000000呢？你确定能申请到这个内存？当然，这个思路已经比较靠近正确答案了。
所有的链表问题，都是指针问题。一个指针不能解决的问题，用两个！一个指针指着当前读取链表，一个滞后m个节点。前面的指针读取到尾节点，滞后的指针所指即为需要的节点。代码如下。
#include <stdio.h>
#include <stdlib.h>
#define N 10
typedef struct NODE{
int data;
struct NODE *next;
}node;
node *init_link()
{
int i;
node *head,*p;
head=(node *)malloc(sizeof(node));
head->data=0;
p=head;
for(i=1;i<N;i++)
{
p->next=(node *)malloc(sizeof(node));
p=p->next;
p->data=i;
}
p->next=NULL;
return head;
}
void print_link(node *head)
{
node *p;
p=head;
while(p!=NULL)
{
printf("%d ",p->data);
p=p->next;
}
printf("\n");
}
node *search_link(node *head,int m)
{
node *front,*back;
int i;
front=head;
back=head;
for(i=0;i<m;i++)
{
if(front->next==NULL)
return NULL;
else
front=front->next;
}
while(front->next!=NULL)
{
front=front->next;
back=back->next;
}
return back;
}
int main()
{
node *head,*result;
int m=1;
head=init_link();
print_link(head);
result=search_link(head,m);
printf("result is %d\n",result==NULL?-1:result->data);
return 0;
}
四、寻找单向链表中的闭合回路
单向链表的解决方法中，经常需要两个指针，比如这个寻找闭合回路的问题。
闭合回路并不一定是循环链表，它也许只是部分循环。
怎么寻找呢？
比较巧妙的就是构造两个指针，一个步长为一，一个为二，跑的快的和跑的慢的会重合。OK，就是有回路了。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 100
typedef struct NODE{
int data;
struct NODE *next;
}node;
node *init_link()
{
int i;
node *head,*p;
node *record;
int record_node;
srand((unsigned)time(NULL));
record_node=rand()%N;
printf("loop point number is %d\n",record_node);
head=(node *)malloc(sizeof(node));
head->data=rand()%1000;
p=head;
for(i=1;i<N;i++)
{
p->next=(node *)malloc(sizeof(node));
p=p->next;
p->data=rand()%100;
//create loop
if(i==record_node)
record=p;
}
p->next=record;
return head;
}
void print_link(node *head)
{
node *p;
p=head;
int i=0;
while(p!=NULL && i<2*N)
{
printf("%d ",p->data);
p=p->next;
i++;
if(i==N)printf("###");
}
printf("\n");
}
int check_loop(node * head)
{
node *fast,*slow;
fast=slow=head;
while(fast->next!=NULL && fast->next->next!=NULL)
{
fast=fast->next->next;
slow=slow->next;
if(fast==slow)
{
return 1;
}
}
return -1;
}
int main()
{
node *head;
head=init_link();
print_link(head);
printf("Is there a loop? %s\n",check_loop(head)?"yes":"no");
return 0;
}
链表的指针就这点小伎俩，很easy吧？
五、寻找单向链表中的中间节点
这个和三里面提到的倒数第m个节点是不是有异曲同工之妙？
当然是采用两个节点，用四里面提到的调节步长。一个跳动一，一个跳动二。跳的快的到来tail，是不是跳的慢的就到中间了？
那有个傻帽的技术面出，寻找三分之一节点呢、三分之二呢？是不是都一个套路？
给出代码前，给些约定。
五个节点，中间节点是第三个，这个没问题。如果有六个呢？你就需要问技术面的人了，是需要给出第三个还是第四个？还是两个都给？当然，details还是需要关注的。这样可以传达出我们对细节的care。这是优秀程序员应该具有的品质。
下面基于6个节点，给第三个算中间节点的方法。当然给出第四个，也就一个next的问题。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 12
typedef struct NODE{
int data;
struct NODE *next;
}node;
node *init_link()
{
int i;
node *head,*p;
srand((unsigned)time(NULL));
head=(node *)malloc(sizeof(node));
head->data=rand()%1000;
p=head;
for(i=1;i<N;i++)
{
p->next=(node *)malloc(sizeof(node));
p=p->next;
p->data=rand()%100;
}
p->next=NULL;
return head;
}
void print_link(node *head)
{
node *p;
p=head;
while(p!=NULL)
{
printf("%d ",p->data);
p=p->next;
}
printf("\n");
}
node* search_middle(node * head)
{
node *fast,*slow;
fast=slow=head;
while(fast->next!=NULL && fast->next->next!=NULL)
{
fast=fast->next->next;
slow=slow->next;
}
return slow;
}
int main()
{
node *head;
node *middle;
head=init_link();
print_link(head);
middle=search_middle(head);
printf("middle node's value is %d\n",middle->data);
return 0;
}
Conclusion
链表要善于用指针，一个不行用两个。步长也可以调。时间复制度控制在O(n)，遍历一遍。同时只是申请指针空间，空间复杂度极低。