[LeetCode] 234. Palindrome Linked List* 解題思路 (Easy)

這題是要判斷這個 LinkedList 是否是回文。

LeetCode 題目連結

 

https://leetcode.com/problems/palindrome-linked-list/

題目

Given a singly linked list, determine if it is a palindrome.

Example 1:

Input: 1->2
Output: false

Example 2:

Input: 1->2->2->1
Output: true

Follow up: Could you do it in O(n) time and O(1) space?

Accept 作法

利用 fast 走兩格， slow 走一個的方式，最終 slow 會走到 LinkedList 的一半，然後在往後做翻轉，去比對 head ，如果相同就是回文。

Runtime: 1 ms
Memory: 41.9 MB

Java 程式碼

class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null){
            return true;
        }
        
        
        ListNode slow = head;
        ListNode fast = head;
        
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        
        if(fast != null){
             slow = slow.next;
        }
        slow = reverse(slow);
        while (slow != null) {
            if (head.val != slow.val) 
                return false;
            head = head.next;
            slow = slow.next;
        }
        return true;
        
        
    }
    
    public ListNode reverse(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }
}

更多 LeetCode 相關資源

• Udemy 暢銷 - Master the Coding Interview: Data Structures + Algorithms

 

複習程式面試書籍

除了 LeetCode 練習外，我也入手了這本，題庫來自真正的面試，並非摘自教科書。它們反映出頂尖公司真正會出的題目，你可以藉此做好充分準備。
需要的話可以看看，寫得很仔細。

 

書名：提升程式設計師的面試力：189道面試題目與解答

• 金石堂實體書資訊
• Hyread 電子書資訊

 

 

相關 LeetCode文章一律會放在 程式解題 標籤分類，歡迎持續追蹤。

⇒ 點我看更多程式解題