Palindrome Linked List
Source
Implement a function to check if a linked list is a palindrome.
Example
Given 1->2->1, return true
Challenge
Could you do it in O(n) time and O(1) space?
Java O(1)
public class Solution {
public boolean isPalindrome(ListNode head) {
if(head==null || head.next==null) return true;
ListNode pre = null;
ListNode slow=head;
ListNode fast=head;
while(fast!=null && fast.next!=null){
pre=slow;
slow=slow.next;
fast=fast.next.next;
}
if(fast!=null){
slow=slow.next;
}
pre.next=null;
head = reverseList(head);
while(head!=null && slow!=null){
if(head.val!=slow.val) return false;
head=head.next;
slow=slow.next;
}
return true;
}
public ListNode reverseList(ListNode head){
ListNode pre = new ListNode(0);
ListNode cur=head;
pre.next=cur;
while(cur!=null && cur.next!=null){
ListNode tmp = cur.next.next;
cur.next.next=pre.next;
pre.next=cur.next;
cur.next=tmp;
}
return pre.next;
}
}
Java O(n) 使用stack
public class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) return true;
Stack<Integer> stack = new Stack<Integer>();
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
stack.push(slow.val);
slow = slow.next;
fast = fast.next.next;
}
if (fast != null) slow = slow.next;
ListNode rCurr = slow;
while (rCurr != null) {
if (rCurr.val != stack.pop()) return false;
rCurr = rCurr.next;
}
return true;
}
}