[TOC]
链表节点的一般定义：
typedef struct ListNode
{
DataType data;
struct ListNode* next;
/* struct ListNode* prev; */ /* 双向链表 */
} ListNodePtr;
从链表还衍生出很多著名的数据结构，比如循环队列、跳表，都值得学习。
常见问题
问题1
给出一个单向链表的头指针，判断是否有环。
思路：俩指针追逐，步进分别为1和2，若有环，这俩指针将相遇。
问题2
给出两个单向链表的头指针，判断这两个链表是否相交。
思路：判断尾指针是否相同，判断有环的情况。
找到相交的那个节点。
思路：需要先遍历两个单向链表，并记录下各自长度；然后，求俩长度之差值，较长的链表先步进该差值，然后再一起步进。
问题3
输入一个单向链表，输出该链表中倒数第k个结点。
思路：设置两个指针p1,p2，首先p1和p2都指向head，然后p2向前走k步，这样p1和p2之间就间隔k个节点，最后p1和p2同时向前移动，直至p2走到链表末尾。
问题4
逆序输出链表。
思路：使用递归，递归结束条件为尾指针，然后逐个弹栈输出。
问题5
输出单链表的中间节点
思路：同样，俩指针追逐，步进分别为1和2，快指针指向链表尾时，慢指针指向中间节点。注意处理奇偶边界即可。