【Leetcode刷題筆記之鏈表篇】234. 回文鏈表

😈博客主頁：🐼大家好我叫張同學🐼
💖 歡迎點贊 👍 收藏 💗留言 📝 歡迎討論！ 👀
🎵本文由 【大家好我叫張同學】 原創，首發于 CSDN 🌟🌟🌟
?精品專欄（不定時更新） 【資料結構+演算法】 【做題筆記】【C語言編程學習】
?? 精品文章推薦
【C語言進階學習筆記】三、字串函式詳解（1）（爆肝吐血整理，建議收藏！！！）
【C語言基礎學習筆記】+【C語言進階學習筆記】總結篇（堅持才有識訓！）

為什么要寫刷題筆記？
寫博客的程序也是對自己刷題程序的梳理和總結，是一種耗時但有效的方法，
當自己分享的博客幫助到他人時，又會給自己帶來額外的快樂和幸福，
（刷題的快樂+博客的快樂，簡直是獎勵翻倍，快樂翻倍有木有QAQ🙈）

給你一個單鏈表的頭節點 head ，請你判斷該鏈表是否為回文鏈表，
如果是，回傳 true ；否則，回傳false ，

原題鏈接（點擊跳轉）

回文結構
從前往后數和從后往前數均相同

從前往后：1 2 2 1
從后往前：1 2 2 1

具有對稱性的鏈表就具有回文結構
如果是單數個結點，中間的結點無需考慮，如果其他結點對稱肯定是回文結構
例如：1 2 3 1 2 也是回文結構

這里借助求鏈表倒數第k個結點的思路，
只要鏈表的

第1個結點=倒數第1個結點
第2個結點=倒數第2個結點
…

一直走到中間結點為止，都相同的話，就是回文結構，否則，就不是回文結構，

回圈結束的進行/終止條件有很多，因為我們事先要求出鏈表的長度，

所以可以通過回圈的步數：step <= 2/length
當然，也可以根據第k個和倒數第k個之間的關系： k <= length-k-1
此外，還可以通過結點指標的關系： cur->next != end || cur != end

bool isPalindrome(struct ListNode* head){
    struct ListNode* tail = head;
    int length = 0;//求鏈表長度
    while(tail){
        tail = tail->next;
        length++;
    } 
    int k = 1;//順數第k個，從1開始
    struct ListNode* cur = head,*end;
    while(k <= length-k){//倒數第k個就是順序第length-k個
        end = head;
        for(int i = 0; i < length-k; i++){
            end = end->next;//通過end找到倒數第k個
        }
        if(cur->val != end->val)//兩者比較，不同就回傳false
            return false;
        cur = cur->next;
        k++;
    }
    return true;//所有結點均比較過，相同，回傳true
}

注意：題目中給出了鏈表結點數量不為0，所以空鏈表不需要考慮，對于僅有一個結點的情況，程式依然能夠覆寫到，所以也不需要作為一個單獨的情況來處理，



通過Leetcode的執行代碼和測驗示例進行預提交，發現程式可以成功通過，但是當我們正式提交的時候，就會出現超出時間限制的問題，
一旦出現超出時間限制，我們通常可以考慮兩種情況
1）程式中某些回圈體結束的條件不對，導致程式進入死回圈，
2）程式演算法的時間復雜度太高，沒達到預期的要求，導致運行超時，
（這時候可能有些同學會問：”妖怪吧，為什么你可以想到我卻想不到呢？“張同學回答：”別問，問就是刷題刷多了，出錯除錯代碼的次數多了，有經驗了，我太難了…每天都是夜深人靜刷力扣，夜靜無人碼代碼_{”，額，開個玩笑}，總之就是多實踐，實踐出真知，實踐是認識的源泉~）


因為程式能通過測驗用例，說明程式不可能顯然死回圈，我們可以點開超出時間限制的測驗用例看一下，然后就可以看到…一大堆…數字，也就是測驗輸入量 n 很大的情況，
程式的時間復雜度為O(n^2)，空間復雜度為O(1) ，當資料量很大的時候，因為O(n^2)的時間復雜度，程式運行的時間就需要很長，自然就無法通過測驗用例，

找到問題后，我們就要思考如何處理這個問題，要想優化時間復雜度，我們會想到以空間換時間的方式，也就是先遍歷一遍原鏈表，將其內容復制頭插到新鏈表中，那么新鏈表的內容實際上就是原鏈表從后往前數的內容，然后通過比較兩個鏈表內容是否相同，來判斷是否為回文結構

我們在第一遍遍歷鏈表復制結點的時候，還可以順便求出鏈表長度，后面比較兩個鏈表的時候，只需要比較前 2/length個結點即可，

bool isPalindrome(struct ListNode* head){
    struct ListNode* cur1 = head;
    struct ListNode* newhead = NULL;
    int length = 0;
    while(cur1){
        //復制結點頭插到newhead新鏈表中
        struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
        node->val = cur1->val;
        if(newhead == NULL){
            newhead = node;
            node->next = NULL;
        }
        else{
            node->next = newhead;
            newhead = node;
        }
        length++;
        cur1 = cur1->next;
    }
    //對比兩個鏈表，判斷回文結構
    cur1 = head;
    struct ListNode* cur2 = newhead;
    int step = length/2;
    while(step--){
        if(cur1->val != cur2->val)
           return false;
        cur1 = cur1->next;
        cur2 = cur2->next;
    }
    return true;
}

提交程式后，Leetcode成功通過，但是我們可以看到程式的執行時間和記憶體消耗都很大，原因如下：
（1）我們實際上遍歷了兩遍鏈表，但重點是我們用malloc開辟新結點構成新鏈表這個的耗時較長，
（2）用malloc開辟新結點組成新鏈表的方式還會占用很多記憶體空間，導致記憶體消耗較大，

注意，新鏈表newhead使用完后要將新鏈表中的結點都釋放掉，因為這種結點都是malloc從堆上面申請的，不釋放會導致記憶體泄漏，如果開發程式使用這段代碼，就會導致電腦或手機記憶體越用越少，程式運行越來越慢！

bool isPalindrome(struct ListNode* head){
    struct ListNode* cur1 = head;
    struct ListNode* newhead = NULL;
    int length = 0;
    while(cur1){
        //復制結點頭插到newhead新鏈表中
        struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
        node->val = cur1->val;
        if(newhead == NULL){
            newhead = node;
            node->next = NULL;
        }
        else{
            node->next = newhead;
            newhead = node;
        }
        length++;
        cur1 = cur1->next;
    }
    //對比兩個鏈表，判斷回文結構
    cur1 = head;
    struct ListNode* cur2 = newhead;
    int step = length/2;
    while(step--){
        if(cur1->val != cur2->val)
           return false;
        cur1 = cur1->next;
        cur2 = cur2->next;
    }
    //釋放newhead鏈表，防止記憶體泄漏
    cur2 = newhead;
    while(cur2){
        struct ListNode* next = cur2->next;
        free(cur2);
        cur2 = next;
    }
    return true;
}

上面這種方法還可以進行小小的改進，原本是復制新結點到鏈表中，再比較兩個鏈表內容是否一致，其實歸根結底就是比較兩個的值是否一樣，因此，我們可以將原鏈表中的val值復制到一個陣列中，陣列的大小可以根據length來確定，malloc一次性開辟一個陣列空間，可以減少消耗，然后再陣列里面內部可以直接比較數值是否相同，（當然也可以用陣列和鏈表比較，只是需要將鏈表前面結點的val和陣列后面的val比較）

那有沒有辦法對其進行改進，以達到程式的運行時間很短，同時記憶體消耗也很小呢？

（1）找中點
（2）反轉前半部分或者后半部分
（3）對比判斷是否為回文結構
（4）還原鏈表

反轉鏈表部分可參考：【Leetcode刷題筆記之鏈表篇】206. 反轉鏈表

//迭代法
struct ListNode* reverseList(struct ListNode* head,struct ListNode* middle){
    if(!head)//先判斷鏈表是否為空
      return NULL;
    struct ListNode* prev = NULL;
    struct ListNode* cur = head;
    while( cur != middle){
        struct ListNode* next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

bool isPalindrome(struct ListNode* head){
    struct ListNode* fast,*slow;
    fast = slow = head;
    while(fast && fast->next){
        slow = slow->next;
        fast = fast->next->next;
    }
    head = reverseList(head, slow);//反轉前半部分
    //通過fast是否為空來判斷結點為單數還是偶數，確定后面比較的起點
    struct ListNode* cur1 = head,*cur2 = slow;
    if(fast != NULL){
        cur2 = cur2->next;
    }
    while(cur1 && cur1 != slow){
        if(cur1->val != cur2->val)
           return false;
        cur1 = cur1->next;
        cur2 = cur2->next;
    }
    //還原
    struct ListNode* mark = head;
    head = reverseList(head,NULL);
    if(mark && mark->next)
       mark->next = slow;
    return true;
}