234. 回文链表
请判断一个链表是否为回文链表。
示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true
进阶:
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题?
解题思路
将后半部分链表反转, 然后设置双指针, 同时遍历。遍历完成后再将链表还原。
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) {
return true;
}
ListNode mid = getMid(head);
ListNode reverseHalf = reverseList(mid);
ListNode preHalf = head;
ListNode postHalf = reverseHalf;
boolean flag = true;
while(preHalf != null && postHalf != null) {
if (preHalf.val != postHalf.val) {
return false;
}
preHalf = preHalf.next;
postHalf = postHalf.next;
}
reverseList(reverseHalf);
return flag;
}
// 当总个数为偶数时, 返回后面一半的第一个元素
// 当总个数为奇数时, 返回中间元素
public ListNode getMid(ListNode head) {
ListNode slow, fast;
slow = fast = head;
while(fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode preNode = null;
ListNode currentNode = head;
ListNode nextNode = currentNode.next;
while (nextNode != null) {
currentNode.next = preNode;
preNode = currentNode;
currentNode = nextNode;
nextNode = nextNode.next;
}
currentNode.next = preNode;
return currentNode;
}