中判斷回文的代碼_LeetCode(234. 回文連結清單) 題解

234. 回文連結清單

題目

請判斷一個連結清單是否為回文連結清單。

何為回文？

維基百科是這樣介紹的：

回文，亦稱回環，是正讀反讀都能讀通的句子，亦有将文字排列成圓圈者，是一種修辭方式和文字遊戲。

北宋文學家蘇轼創作的一首名為《菩薩蠻·回文夏閨怨》的詞，就用到了回文的修辭方式。

菩薩蠻·回文夏閨怨 

蘇轼

柳庭風靜人眠晝。晝眠人靜風庭柳。

香汗薄衫涼。涼衫薄汗香。

手紅冰碗藕。藕碗冰紅手。

郎笑藕絲長。長絲藕笑郎。

這首《夏閨怨》大意呢是上片寫閨人晝寝的情景，下片寫醒後的怨思。各位看官感受一下回文的妙處，至于詩歌賞析暫且按住不表，有興趣的看官可以自行查閱解析。

回顧

之前做過判斷回文的相似題，還記得怎麼解嗎：LeetCode(125. 驗證回文串) 題解。

當時提到了兩種解法，一種原地翻轉，一種雙指針。同樣也适用于解這道題。差別在于125題是字元串，本題是單連結清單。基于單連結清單的線性的鍊式存儲結構的特點，這裡就需要一點點小技巧進行相應的轉化與處理。

思路1-原地翻轉

對于字元串的原地翻轉，可以通過Java的API實作，也可以使用雙指針的辦法，手寫一個原地翻轉的函數。單連結清單，不能通路前驅節點，可以利用棧後入先出的特性，周遊一遍單連結清單将連結清單中的節點入棧，然後棧頂元素依次出棧和連結清單周遊比較，判斷翻轉後的連結清單是否與原連結清單相等。

上代碼

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { val = x; } * } */class Solution {    public boolean isPalindrome(ListNode head) {        if(head == null || head.next == null) return true;        Stack stack = new Stack<>();        ListNode node = head;        while(node != null){            stack.push(node);            node = node.next;        }        while(head != null && !stack.isEmpty()){            ListNode tmpNode = stack.pop();            if(head.val != tmpNode.val) return false;            head = head.next;        }        return true;    }}
           

思路2-雙指針法之快慢指針

對于字元串的雙指針法，初始時，左右指針分别指向字元串的兩側，左指針左移，右指針右移，每次移動一步，并判斷這兩個指針指向的字元是否相同。對于連結清單，右指針右移的部分應該怎麼處理呢？可以通過快慢指針法找到連結清單的中間節點，将後半部分翻轉，然後兩個連結清單依次周遊進行比較。後半部分翻轉後的周遊相當于右指針右移部分。

上代碼

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { val = x; } * } */class Solution {    public boolean isPalindrome(ListNode head) {        if(head == null || head.next == null) return true;        //快慢指針        ListNode fastNode = head;        ListNode slowNode = head;        //快指針走兩步 慢指針走一步 找到連結清單中點        while(fastNode.next != null && fastNode.next.next != null){            slowNode = slowNode.next;            fastNode = fastNode.next.next;        }        //将後半部分反轉        ListNode newHead = null;        ListNode curr = slowNode.next;        while(curr != null){            ListNode tmpNode = curr.next;            curr.next = newHead;            newHead = curr;            curr = tmpNode;        }        //兩部分進行比較判斷        while(head != null && newHead != null){            if(head.val != newHead.val) return false;            head = head.next;            newHead = newHead.next;        }        return true;    }}
           

分析

這種解法的優點在于沒有開辟額外的記憶體空間，算法的空間複雜度為O(1)。

思路3-雙指針法

雙指針法需要左右指針進行周遊判斷，對于連結清單無法實作，可将連結清單進行轉換，将其複制到清單或數組中，使之可以使用左右指針相向而行的方法進行判斷。

上代碼

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { val = x; } * } */class Solution {    public boolean isPalindrome(ListNode head) {        if(head == null || head.next == null) return true;        List list = new ArrayList<>();        while(head != null){            list.add(head);            head = head.next;        }        int left = 0;        int right = list.size() - 1;        while(left < right){            if(list.get(left).val != list.get(right).val) return false;            left ++;            right --;        }        return true;    }}
           

思路4-遞歸

還有一種遞歸的解法，參照 思路2-原地翻轉的思想，連結清單可以使用遞歸的方法進行逆序周遊，那麼将逆序周遊的結果與原連結清單進行比較就可以完成判斷。參考官方題解連結[1]。

上代碼

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { val = x; } * } */class Solution {    ListNode front = null;    public boolean isPalindrome(ListNode head) {        if(head == null || head.next == null) return true;        front = head;        return recursion(head);    }    public boolean recursion(ListNode head){        if(head == null) return true;        boolean res = recursion(head.next);        if(head.val != front.val) return false;        front = front.next;         return res;    }}
           

References

[1] https://leetcode-cn.com/problems/happy-number/solution/kuai-le-shu-by-leetcode-solution/

程式員畫工師｜歡迎關注

持續分享Java相關程式設計技術、資料結構與算法