【leetcode刷題】19.回文連結清單——Java版

前言

哈喽，大家好，我是一條。

糊塗算法，難得糊塗

周末肝了四篇文章，累趴了

Question

234. 回文連結清單

難度：簡單

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

示例 1:

輸入: 1->2
輸出: false      

示例 2:

輸入: 1->2->2->1
輸出: true      

進階：

你能否用 O(n) 時間複雜度和 O(1) 空間複雜度解決此題？

Solution

相信大家都做過“回文”數字這道題，所謂回文就是正序和倒序周遊的結果是一樣的。

那想想我們昨天做的題，正好是反轉連結清單，是以我們就可以利用棧先進後出的特性先放進去，再拿出來比對，如果都相等，就是回文連結清單。

對于快慢雙指針，其實也是利用翻轉的思想，隻不過是前半部分和後半部分比較。快慢指針的作用是找到中間的結點。慢指針一次走一步，快指針一次走兩步，快慢指針同時出發。當快指針移動到連結清單的末尾時，慢指針恰好到連結清單的中間。通過慢指針将連結清單分為兩部分。

建立一個棧，記錄兩個等于head的連結清單，一個用來壓入棧，一個用來出棧時的比較。

入棧

出棧比較

有不同的傳回false

Code

所有leetcode代碼已同步至github

歡迎star

/**
 * @author yitiaoIT
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        Stack<Integer> stack = new Stack<>();
        ListNode l1=head;
        ListNode l2=head;
        while (l1!=null){
            stack.push(l1.val);
            l1=l1.next;
        }
        while (!stack.isEmpty()){
            if(stack.pop()!=l2.val){
                return false;
            }
            l2=l2.next;
        }
        return true;
    }
}      

Result

複雜度分析

• 時間複雜度：O(N)

🌈尋寶

⭐今天是堅持刷題更文的第19/100天

⭐各位的點贊、關注、收藏、評論、訂閱就是一條創作的最大動力

⭐更多算法題歡迎關注專欄《leetcode》

為了回饋各位粉絲，禮尚往來，給大家準備了一條多年積累下來的優質資源，包括 學習視訊、面試資料、珍藏電子書等

怎麼領取請大家自己找，尋寶遊戲現在開始。

找不到可以評論留言，一條就會注意到你。

如果還不行，請私信我。