[Leetcode] 234. Palindrome Linked List

題目敘述

Given the head of a singly linked list, return true if it is a palindrome or false otherwise.

A palindrome is a sequence that reads the same forward and backward.

Example 1.

Input: head = [1,2,2,1]
Output: true

Example 2.

Input: head = [1,2]
Output: false

限制:

The number of nodes in the list is in the range [1, 105].
0 <= Node.val <= 9

Follow up:

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

解題思路：

這一題是要判斷這個 linked list 是否是回文形式。所以重點有兩個：

找出中間點，這樣才能找出回文的斷點，以利後續做比較
判斷是否為回文，就是要把前半從前面看跟後半從後面看作比較，如果全部相同就是回文，有任何不同就不是。而這邊因為題目給的是 Single Linked List，所以沒辦法從後面往前看，我們就只能把後半的 Linked List 顛倒過來（前後交換）。

解題步驟：

寫兩個 helper function findFirstHalfEnd 和 reverseList
1. findFirstHalfEnd：
  1. 宣告兩個 pointer slow 和 fast
  2. 在 fast 還沒有碰到底之前進行迴圈
    1. fast 往後走兩個 node
    2. slow 往後走一個 node
  3. 當 fast 碰到底時，因為他走了 slow 兩倍的 node，所以這時後 slow 指向的就是整個 linked list 的中心點
2. reverseList：這個在另外一題有講解過，可以看這篇文章
利用 findFirstHalfEnd 找到中心點之後利用 reverseList 把中心點後的 node 顛倒過來（前後交換）
比較前半（中心點以前）和顛倒過後的後半 Linked List，如果有如果有任何一個 node 的 value 不同代表他不是回文，所以回傳 false，如果全部相同則回傳 true

Java 解法

class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null) return true;
 
        ListNode firstHalfEnd = findFirstHalfEnd(head);
        ListNode reversedSecondHalfStart = reverseList(firstHalfEnd.next);
 
 
        ListNode p1 = head;
        ListNode p2 = reversedSecondHalfStart;
 
        while (p2 != null) {
            if (p1.val != p2.val) return false;
            p1 = p1.next;
            p2 = p2.next;
        }
 
        return true;
 
    }
 
    public ListNode findFirstHalfEnd(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
 
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
 
    public ListNode reverseList(ListNode head) {
        ListNode previous = null;
        ListNode current = head;
 
        while (current != null) {
            ListNode nextTemp = current.next;
 
            current.next = previous;
            previous = current;
            current = nextTemp;
        }
 
        return previous;
    }
}

Complexity

Time Complexity: O(n);
Space Complexity: O(1);