PattySung

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

Example 1:

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

Example 2:

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

<解題>

1.把LinkedList分成一半來判斷

<說明>

把LinkedList分成一半
反轉其中一半
從頭開始比較每個節點的值，如果不同就return false；如果全部都相同就return true


class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true; 
        }

        ListNode fast = head;
        ListNode slow = head;

        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        ListNode secondHalf = reverse(slow.next);

        while (secondHalf != null) {
            if (head.val != secondHalf.val) {
                return false; 
            }
            head = head.next;
            secondHalf = secondHalf.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;
    }
}

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

2. 用兩指標分別從頭尾往內跑，檢驗是否相等


class Solution {
    public boolean isPalindrome(ListNode head) {
    if(head == null | head.next ==null) return true;
		List<Integer> l = new ArrayList<>();
		while(head!=null){
			l.add(head.val);
			head = head.next;
		}

		int start =0 , end = l.size()-1;
		while(start<end){
			if(l.get(start)!= l.get(end)) return false;
			start++;
			end--;
		}
		return true;
    }
}

Time: O(n) Space: O(n)

Leetcode-234. Palindrome Linked List

<解題>

1.把LinkedList分成一半來判斷

2. 用兩指標分別從頭尾往內跑，檢驗是否相等