链表求中点以及回文检测

以前见到一个题目，求链表的倒数第K个结点。实现方式很巧妙：

1. 让一个指针先走K步
2. 然后另一个指针从头开始，两者同时开始走。
3. 前指针走完了，那后指针一定是在倒数第K个位置。

求链表的中点问题，也可以利用这种思路：

1. 前指针一次走两步，后指针一次走一步。
2. 前指针走完了，后指针一定在中间位置。

当然，这其中也有很多问题，比如结点数目是奇数偶数的时候，中间位置怎么定义。
在这里，我们定义结点编号从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;
    }