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?
给定一个单链表，判断是否是回文链表
算法分析
首先产生该链表的逆序链表，然后比较两个链表的前半部分即可。
Java代码
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public boolean isPalindrome(ListNode head) {
//创建一个逆序的链表
ListNode node = head;
ListNode tail = null;
int counter = 0;
while (node != null) {
ListNode temp = new ListNode(node.val);
temp.next = tail;
tail = temp;
node = node.next;
counter++;
}
counter /= 2;
//比对原链表与逆序链表是否一致
while (counter != 0) {
counter--;
if (tail.val != head.val) {
return false;
}
head = head.next;
tail = tail.next;
}
return true;
}
}
