以前见到一个题目，求链表的倒数第K个结点。实现方式很巧妙：
- 让一个指针先走K步
- 然后另一个指针从头开始，两者同时开始走。
- 前指针走完了，那后指针一定是在倒数第K个位置。
求链表的中点问题，也可以利用这种思路：
- 前指针一次走两步，后指针一次走一步。
- 前指针走完了，后指针一定在中间位置。
当然，这其中也有很多问题，比如结点数目是奇数偶数的时候，中间位置怎么定义。
在这里，我们定义结点编号从1开始到N，中间结点是N/2向下取整。
ListNode* mid(ListNode* pHead) {
ListNode* H=new ListNode(0);
H->next=pHead;
ListNode* fast=H,*slow=H;
while(fast->next && fast->next->next){
fast=fast->next->next;
slow=slow->next;
}
ListNode* m=slow;
delete H;
return m;
}
注意
在这里我手动加了个头结点，来完成这个过程。其实多数情况下带头结点的链表用起来会方便很多。
链表回文检测
检测链表的回文结构，最容易的方式就是把链表内容拷贝进入数组中进行检测，但是需要O(N)的额外空间。
这里提供的方法是找到链表的中点，然后把链表后半部分反转。这样从链表的首尾就可以开始检测，逐个比对。
无论是奇数还是偶数，遍历过程都是一样的，m2都是在N/2的位置。检测的时候尾指针从right一直遍历到空即可。
注意slow和m2的链接没有改变。
注意判断完以后把链表及时纠正回来。
bool isPalindrome(ListNode* pHead) {
// write code here
ListNode* H=new ListNode(0);
H->next=pHead;
ListNode* fast=H,*slow=H;
while(fast){
if(fast->next && fast->next->next){
fast=fast->next->next;
slow=slow->next;
}else{
break;
}
}
ListNode* m2=slow->next;
ListNode* right=reverL(m2,nullptr);
ListNode* h1=pHead,*h2=right;
bool match=1;
while(h2){
if(h1->val!=h2->val){
match=0;
break;
}else{
h1=h1->next;
h2=h2->next;
}
}
m2=reverL(right,nullptr);
delete H;
return match;
}
