总结了编程之美上面关于链表的题目，有不正确的地方，欢迎拍砖，等编程之美看完了，回头刷其他题时遇到链表再补充~
目录如下（点击展开上面的目录到感兴趣的题目）：
/************************************************************************//* 链表经典练习题 1.从无头链表中删除节点 2.链表逆转 3.判断两个链表是否相交 4.如何检查链表是否存在环 5.求带环链表中环的长度 6.求有环单链表的环连接点位置 7.如果链表可能有环，判断两链表是否相交，并求相交的第一个节点*//************************************************************************/
1.从无头链表中删除节点
题目描述：给定一个无头指针的单链表，一个指针指向既非第一个结点也非最后一个结点，要求把该指针指向的结点删除
思路：这道题来自编程之美，在226页。起初第一次看到这道题时，觉的似乎无法删除，看了答案才恍然大悟，思路是删除该指针后面的结点，把删除后结点数据域的内容提前覆盖到该指针结点的数据域，实在巧妙，代码如下：
//1.从无头链表中删除节点void DeleteNode(pNode p){if (NULL == p)//保证p的合法性{return;}pNode next = p->pNext;//要删除节点的下一个节点if (next != NULL)//保证待删除节点并非最后一个节点{p->data = next->data;//数据域内容覆盖p->pNext = next->pNext;//删除next指向的节点delete next;next = NULL;}}
2.链表逆转
题目描述：给定一个带头指针的单链表，要求只遍历一次，将链表元素顺序翻转过来
思路：这道题来自编程之美中无头链表中删除节点的扩展问题，页码为228。这个题目的思路跟前插法建立链表很像，用一个扫描指针遍历链表，将当前扫描指针指向的节点插入到链表第一个节点，实现过程中有一关键的指针变量，它始终指向链表的第一个节点。这样的方法时间复杂度为O(N), 空间复杂度为O(1)，代码如下：
//2.链表逆转void ReverseList(pNode pHead){//仅1个节点的链表直接返回，无需逆转if (NULL == pHead->pNext || NULL == pHead->pNext->pNext){return;}pNode p = pHead->pNext;//扫描指针pNode pFirst = p;//总是指向链表中第一个有效节点pNode pTempFirst = p;//记录当前第一个节点地址p = p->pNext;//扫描指针直接从第2个节点开始while (p != NULL){pNode tempNext = p->pNext;//暂存当前节点所指的下一个节点地址pHead->pNext = p;//下面步骤将当前节点插入到第一个节点p->pNext = pFirst;pFirst = p;//更新pFirstp = tempNext;//扫描指针移动}pTempFirst->pNext = NULL;//逆转链表最后一个元素收尾}
3.判断两个链表是否相交
题目描述：给两个单链表，判断它们是否相交，假设两个链表都不带环
思路：这道题来自编程之美的233页，如果两个链表相交，那么它们一定会在某个节点开始有重合，一直到末尾也是重合的，所以一个比较简单的判断方法就是将两个链表遍历到尾，比较这两个节点是否是同一个节点，这样的时间复杂度为O(|L1|+|L2|)，L1,L2表示两个链表，代码如下：
//3.判断两个链表是否相交bool IsIntersect(pNode L1, pNode L2){if (NULL == L1 || NULL == L2|| NULL == L1->pNext|| NULL == L2->pNext)//头指针非法,或有空链表{return false;}//遍历L1,让L1指向最后一个节点while (L1->pNext != NULL){L1 = L1->pNext;}//遍历L2,让L2指向最后一个节点while (L2->pNext != NULL){L2 = L2->pNext;}//判断最后的节点是否为同一个return (L2 == L1);}
4.如何检查链表是否存在环
题目描述：给定一个单链表，怎样检查链表是否存在环
思路：如果一个单链表存在环状，如果直接遍历无视一个无限循环，可以用两个指针，一个称之为慢指针pSlow，每次向前一步，另一个快指针pFast，可以让它一次向前两步，如下图，这样在环中，肯定是快的在追慢的，并且一定会相遇的，如果单链表没有环，最后的结果肯定是pFast = NULL了。代码如下：
//4.如何检查链表是否存在环bool IsCircle(pNode pHead){pNode pFast = pHead;pNode pSlow = pHead;//如果是不含环单链表,循环以pFast==null或者pFast->pNext==null退出//如果含环,则循环以pFast==pSlow退出while (pFast != NULL && pFast->pNext != NULL){pFast = pFast->pNext->pNext;//走两步pSlow = pSlow->pNext;//走一步if (pSlow == pFast){break;}}return (pFast == pSlow);}
5.求带环链表中环的长度
题目描述：给定一个带环的链表，如何计算它的环长是多少
思路：这个是一个典型的追击问题，关键点当快慢指针在第一次相遇到第二次相遇时，快指针比慢指针多跑的路程就是圆环的长度，这个关键点用下面的图可以清楚的理解，快指针橙色多跑的路程减去蓝色慢指针跑的路程就是环长。代码如下：
其实只要你愿意，一切都可以变得很容易。
