234. Palindrome Linked List

难度: Easy

题目描述

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

 

Constraints:

• 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?

解题思路

代码实现

解决方案

java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {

        List<Integer> list = new ArrayList<>();
        ListNode prev = head;
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null) {
            prev = slow;
            slow = slow.next;
            fast = fast.next;
            if (fast != null) {
                fast = fast.next;
            }

        }
        prev.next = null;
        while (slow != null) {
            ListNode insert = slow;
            slow = slow.next;
            insert.next = null;
            ListNode prevNext = prev.next;
            prev.next = insert;
            insert.next = prevNext;

        }
        ListNode headP = head;
        ListNode startP = prev.next;
        while (startP != null) {
            if (headP.val != startP.val) {
                return false;
            }
            headP = headP.next;
            startP = startP.next;
        }

        return true;

    }
}