234 Palindrome Linked List

1. Question

Given a singly linked list, determine if it is a palindrome.
Follow up: Could you do it in O(n) time and O(1) space?

2. Implementation

1
/**
2
* Definition for singly-linked list.
3
* public class ListNode {
4
* int val;
5
* ListNode next;
6
* ListNode(int x) { val = x; }
7
* }
8
*/
9
class Solution {
10
public boolean isPalindrome(ListNode head) {
11
if (head == null || head.next == null) {
12
return true;
13
}
14
15
ListNode fast = head, slow = head;
16
17
while (fast.next != null && fast.next.next != null) {
18
fast = fast.next.next;
19
slow = slow.next;
20
}
21
22
slow = reverseList(slow.next);
23
fast = head;
24
25
while (slow != null) {
26
if (fast.val != slow.val) {
27
return false;
28
}
29
fast = fast.next;
30
slow = slow.next;
31
}
32
return true;
33
}
34
35
public ListNode reverseList(ListNode curNode) {
36
ListNode preNode = null, nextNode = null;
37
38
while (curNode != null) {
39
nextNode = curNode.next;
40
curNode.next = preNode;
41
preNode = curNode;
42
curNode = nextNode;
43
}
44
return preNode;
45
}
46
}
Copied!

3. Time & Space Complexity

时间复杂度O(n), 空间复杂度O(1)