leetcode 234. 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?
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
List<Integer> list = new ArrayList<>();
while(head != null){
list.add(head.val);
head = head.next;
}
int start = 0;
int end = list.size()-1;
while(end - 1 >= start){
if(!list.get(start).equals(list.get(end))) return false;
end--;
start++;
}
return true;
}
}
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
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;
}
fast = head;
int length = 0;
while(fast != null) {
length++;
fast = fast.next;
}
fast = head.next;
head.next = null;
while(fast != slow){
ListNode temp = fast.next;
fast.next = head;
head = fast;
fast = temp;
}
if(length % 2 != 0) slow = slow.next;
while(head!= null && slow!= null){
if(head.val != slow.val) return false;
head = head.next;
slow = slow.next;
}
return true;
}
}
页:
[1]