正文
leetcode234 回文链表 两种做法（stack(空间非O(1)），空间O(1)）
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
link: leetcode234 回文链表
方法1， 快慢指针，把前半部分存入栈中和后半部分比较
public boolean isPalindrome(ListNode head) {
if(head == null || head.next == null) return true;
Stack<Integer> stack = new Stack<>();
ListNode slow = head;
ListNode fast = head;
while(true){
stack.push(slow.val);
slow = slow.next;
if(fast.next == null){//odd
stack.pop();
break;
}
if(fast.next.next == null){ //even
break;
}
fast = fast.next.next;
}
boolean flag = true;
while (!stack.empty() && slow != null){
int temp = stack.pop();
if(slow.val == temp){
slow = slow.next;
}else {
flag = false;
break;
}
}
if(!stack.empty() || slow != null)
flag = false;
return flag;
}
方法2， 快慢指针，把前半部分反转与后半部分比较
public boolean isPalindrome2(ListNode head) { // O(1)
if(head == null || head.next == null) return true;
if(head.next.next == null){
if(head.next.val == head.val){
return true;
}else{
return false;
}
}
ListNode slow = head;
ListNode fast = head;
int cnt= 0;
while(true){
slow = slow.next;
cnt ++;
if(fast.next == null){//odd
cnt --;
break;
}
if(fast.next.next == null){ //even
break;
}
fast = fast.next.next;
}
// System.out.println("after while, slow.val =" +slow.val);
ListNode fan = head;
ListNode temp = head;
ListNode newHead = head;
int n = 0;
// System.out.println("cnt= " + cnt);
while (n < cnt - 1){
temp = fan.next;
fan.next = fan.next.next;
temp.next = newHead;
newHead = temp;
// System.out.println("temp =" +temp.val);
n++;
}
fan.next = null;
boolean f = true;
while(true){
// System.out.println(slow.val + " | " + newHead.val);
if(slow.val == newHead.val){
slow = slow.next;
newHead = newHead.next;
}else {
f = false;
break;
}
if(slow == null && newHead != null){
f = false;
break;
}else if(slow != null && newHead == null){
f = false;
break;
}else if(slow == null && newHead == null){
break;
}
}
return f;
}
