Description
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?
Solution
要求时间复杂度为O(n)，空间复杂度为O(1)。
那么我们将链表进行切分，然后翻转进行比较。
/**
* 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, fast = head.next;
while(fast != null && fast.next != null){ //保证fast在最后会停下来，利用fast速度是slow的两倍，slow达到链表中间
slow = slow.next;
fast = fast.next.next;
}
if(fast != null) //偶数个节点，slow指向下一个作为切分链表的头
slow = slow.next;
cut(head, slow); //切分链表
return isEqual(head, reverse(slow)); //比较切分链表翻转后的两个链表
}
private void cut(ListNode head, ListNode cutNode){
while(head.next != cutNode) //将head指向cutNode的前一个
head = head.next;
head.next = null;
}
private ListNode reverse(ListNode head){
ListNode newHead = null;
while(head != null){
ListNode nextNode = head.next; //记下下一个节点
head.next = newHead; //将head连接在newHead链表的头部
newHead = head; //更新newHead指向新链表的第一个
head = nextNode; //更新head指向原链表的下一个
}
return newHead;
}
private boolean isEqual(ListNode l1, ListNode l2){
while( l1 != null && l2 != null){ //这里当两个其中一个为空时就退出返回true，当时奇数个节点时，l2会比l1多一个节点，
if(l1.val != l2.val) //也就是原链表的中间节点，在l2的最后一个，但此时l1已经为空，所以退出返回true。
return false; //这样就不需要额外的代码再去处理原链表结点数目为奇数时的情况
l1 = l1.next;
l2 = l2.next;
}
return true;
}
}