王道数据结构P40 T5 单链表就地逆置

逆置法：遍历每个结点，并将每个结点用头插法重新插入到头结点。

辅助指针法：改变每个结点的前驱和后继，最后将头结点指向最后一个结点，作为新表的第一个结点。

王道数据结构P41 T8 给定两个单链表，求两个链表的第一个公共结点

两个单链表有公共结点，一定是Y型而非X型的。

1. 分别遍历两表，获取表长s1与s2
2. 用指针p从头结点遍历长的表，让p移动|s1-s2|个结点
3. 再用指针q指向头结点，p、q同时移动，直到表尾。
4. 若移动过程中存在p、q所指结点相等，则该结点为第一个公共结点。

一个单链表中只给当前结点的指针，如何删除当前结点？

根据已有条件将问题转化，因无法获取当前结点的前驱，但我们能获取当前结点的后继。

将后继结点的值覆盖当前结点，将“删除当前结点”转化为“删除当前结点的后继结点”，这样便有了前驱，删除即可。

王道数据结构P42 T21中，只给头指针，查找倒数第k个结点

先后双指针法，p先移动k个结点后，p、q同时移动，直到p移动到表尾，此时q移动到导数第k个结点。

王道数据结构P44 T24中，如何判断链表中是否有环？

快慢双指针法，p和q同时从头结点出发，p每次走1步，q每次走2步，经若干步后，若p和q都没有走到表尾，而p和q却指向同一结点，则说明链表有环，否则无环。

王道数据结构P44 T25中，如何高效的求表的中间结点？

快慢双指针法，p和q同时从头结点出发，p每次走1步，q每次走2步，当q走到表尾，此时q走到表的中间。