由于前面写了一些数据结构的相关的文章，但是都是偏基本的数据结构知识，并没有实际的算法题加以实践，故整理十道题目，都是比较常见的链表类的算法题，也参考了优秀的博客。
预备的数据结构知识点：
数据结构绪论
循序渐进学习栈和队列
循序渐进学习数据结构之线性表
循序渐进学习时间复杂度
输入一个链表，输出该链表中倒数第k个结点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾结点是倒数第1个结点。例如一个链表有6个结点，从头结点开始它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个结点是值为4的结点,需要保证时间复杂度。
设置两个指针p1,p2，从头到尾开始出发，一个指针先出发k个节点，然后第二个指针再进行出发，当第一个指针到达链表的节点的时候，则第二个指针表示的位置就是链表的倒数第k个节点的位置。
总结：当我们用一个指针遍历链表不能解决问题的时候，可以尝试用两个指针来遍历链表。可以让其中一个指针遍历的速度快一些（比如一次在链表上走两步），或者让它先在链表上走若干步。
2.从尾到头打印链表（递归和非递归） 问题描述：输入一个单链表链表，从尾到头打印链表每个节点的值。输入描述：输入为链表的表头；输出描述：输出为需要打印的“新链表”的表头。
算法思路：首先我们想到从尾到头打印出来，由于单链表的查询只能从头到尾，所以可以想出栈的特性，先进后出。所以非递归可以把链表的点全部放入一个栈当中，然后依次取出栈顶的位置即可。
代码如下： //非递归 void PrintReversing(ListNode * head){ //利用一个栈 Stack stack; ListNode *node=head->next; //将链表的结点压入 while(node!=null){ stack.push(node); node=node->next; } ListNode *popNode; while(stack.isEmpty()){ //获得最上面的元素 popNode=stack.top(); //打印 printf("%d\t",popNode->value); //弹出元素 stack.pop(); } /递归 void printRevese(ListNode *head){ if(head!=null){ if(head->next!=null){ printRevese(head->next); } print("%d\t",head->value); } }非递归的描述当中，经常会用栈或者队列这些数据结构来改写一些递归的算法。其实递归的算法的时间复杂度是递归树的高度，所以递归的层数越高，时间复杂度也就会越高的。
3.如何判断一个链表有环 问题描述：有一个单向链表，链表当中有可能出现“环”，如何用程序判断出这个链表是有环链表？
不允许修改链表结构。时间复杂度O(n)，空间复杂度O(1)。
首先从头节点开始，依次遍历单链表的每一个节点。每遍历到一个新节点，就从头节点重新遍历新节点之前的所有节点，用新节点ID和此节点之前所有节点ID依次作比较。如果发现新节点之前的所有节点当中存在相同节点ID，则说明该节点被遍历过两次，链表有环；如果之前的所有节点当中不存在相同的节点，就继续遍历下一个新节点，继续重复刚才的操作。
假设从链表头节点到入环点的距离是D，链表的环长是S。那么算法的时间复杂度是0+1+2+3+….+(D+S-1) = (D+S-1)(D+S)/2 ， 可以简单地理解成 O(NN)。而此算法没有创建额外存储空间，空间复杂度可以简单地理解成为O(1)。
这种方法是暴力破解的方式，时间复杂度太高。
方法二、快慢指针首先创建两个指针1和2，同时指向这个链表的头节点。然后开始一个大循环，在循环体中，让指针1每次向下移动一个节点，让指针2每次向下移动两个节点，然后比较两个指针指向的节点是否相同。如果相同，则判断出链表有环，如果不同，则继续下一次循环。
说明 ：在循环的环里面，跑的快的指针一定会反复遇到跑的慢的指针 ，比如：在一个环形跑道上，两个运动员在同一地点起跑，一个运动员速度快，一个运动员速度慢。当两人跑了一段时间，速度快的运动员必然会从速度慢的运动员身后再次追上并超过，原因很简单，因为跑道是环形的。