以前見到一個(gè)題目，求鏈表的倒數(shù)第K個(gè)結(jié)點(diǎn)。實(shí)現(xiàn)方式很巧妙：

1. 讓一個(gè)指針先走K步
2. 然后另一個(gè)指針從頭開始，兩者同時(shí)開始走。
3. 前指針走完了，那后指針一定是在倒數(shù)第K個(gè)位置。

求鏈表的中點(diǎn)問題，也可以利用這種思路：

1. 前指針一次走兩步，后指針一次走一步。
2. 前指針走完了，后指針一定在中間位置。

當(dāng)然，這其中也有很多問題，比如結(jié)點(diǎn)數(shù)目是奇數(shù)偶數(shù)的時(shí)候，中間位置怎么定義。
在這里，我們定義結(jié)點(diǎn)編號(hào)從1開始到N，中間結(jié)點(diǎ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;
    }

注意

在這里我手動(dòng)加了個(gè)頭結(jié)點(diǎn)，來完成這個(gè)過程。其實(shí)多數(shù)情況下帶頭結(jié)點(diǎn)的鏈表用起來會(huì)方便很多。

鏈表回文檢測(cè)

檢測(cè)鏈表的回文結(jié)構(gòu)，最容易的方式就是把鏈表內(nèi)容拷貝進(jìn)入數(shù)組中進(jìn)行檢測(cè)，但是需要O(N)的額外空間。
這里提供的方法是找到鏈表的中點(diǎn)，然后把鏈表后半部分反轉(zhuǎn)。這樣從鏈表的首尾就可以開始檢測(cè)，逐個(gè)比對(duì)。

無論是奇數(shù)還是偶數(shù)，遍歷過程都是一樣的，m2都是在N/2的位置。檢測(cè)的時(shí)候尾指針從right一直遍歷到空即可。
注意slow和m2的鏈接沒有改變。
注意判斷完以后把鏈表及時(shí)糾正回來。

    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;
    }