#数据结构#
数据结构是所有计算机科学相关专业的必修课之一，很多学校的数学专业也会将这门课作为必修课，可见这门科目的重要性。如果有志考计算机方面的研究生，数据结构对于大部分学校都是一个必考的知识，尤其在统考中，是分数占比最大的一个科目。而对于计算机软件相关的工作者而言，虽然大部分时候不会直接手动构建数据结构，但是数据结构仍然是相关工作者不可或缺的技能，对于优化程序细节，减小运算复杂度方面尤为重要。
链表作为除顺序表外最基础的数据结构，和顺序表（顺序遍历的数组）一起作为更上层的数据结构的底层结构。最基本的单链表是线性表的一种，顾名思义，表中的元素有明显的线性关系，可以参考顺序表，有明显的从前到后的顺序。不过链表和顺序表不同，数组的元素一定是分配在一块连续的内存上，而链表不同，链表的元素在内存上并没有直接的关系，跟分配的时机，内存堆空闲内存块的大小，分配内存的方法等等有关。
链表由一个个结点连接而成，形似一条铁链，环环相扣，因此称为链表，链表结点由至少两部分组成，一个是要存储的元素，另一个是下个结点的地址（指针域）。第二部分可以有多种实现，既可以使用指针进行动态分配，即一般的链表，也可以使用数组存储链表，数组元素的序号作为地址，这种称为静态链表，在没有指针概念的语言里经常使用。单链表的最后一个结点的指针域通常为空指针，如果不为空，而是指针指向该链表中的某一个结点，就会成环，指向的结点是第一个结点的时候称该链表为循环链表。
链表的基本操作包括创建链表、插入结点、删除结点、读取结点，销毁链表等。简单来讲就是数据库中的CRUD。一个经典的，关于链表的面试题就是反转链表。一般关于链表的问题先画图，能做到事半功倍的效果。
反转链表的一个方法如图所示，head是链表的头指针，指向链表的第一个结点，ptr是一个指针变量，在反转的过程中会更新成*head的指针域，同时我们需要一个另外的辅助指针变量last用于反转指向。反转链表的该算法可以描述如下：先定义ptr和last，head为所给链表头指针，ptr初始化为head，当*head的指针域不为空时，执行循环，令last保存*head指针域所指结点的指针域，改变这个指针域，使其等于ptr，ptr迭代为*head的指针域，而*head的指针域更新为last的值，然后返回判断，知道退出循环，退出循环后ptr的值就是我们反转后链表的头指针。其C代码的描述如下所示。
除了这个方法之外，还有一种更容易理解的办法，就是原地反转指向，然后迭代循环，最后修改*head的指针域为NULL，返回用于迭代的非空指针即可。