描述
请判断一个链表是否为回文链表。
示例
示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true
思路
1>暴力解法
反转整个链表，然后遍历对比一遍即可。时间复杂度O(N)，空间复杂度O(1)
2>优化
快慢指针遍历链表找到中间节点，然后将后半部分反转，再从头和从反转之后的头开始遍历对比，时间复杂度O(N)，空间复杂度O(1)
3>利用栈反转
时间复杂度O(N)，空间复杂度O(N)
代码
/**
* 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){
slow = slow.next;
fast = fast.next.next;
}
slow = reserve(slow);
while(slow != null && slow != head){
if(head.val != slow.val){
return false;
}
slow = slow.next;
head = head.next;
}
return true;
}
//反转链表
public ListNode reserve(ListNode head){
if(head == null || head.next == null){
return head;
}
ListNode before = null;
while(head != null){
ListNode next = head.next;
head.next = before;
before = head;
head = next;
}
return before;
}
}
