LeetCode刷题实战234:回文链表
共 3532字,需浏览 8分钟
·
2021-04-09 14:02
Given the head of a singly linked list, return true if it is a palindrome.
示例
示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true
进阶:
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题?
解题
class Solution {
public boolean isPalindrome(ListNode head) {
ListNode fast = head;
ListNode slow = head;
if (fast == null || fast.next == null) return true;
while (fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
ListNode newHead = reverseList(slow.next);
while (newHead != null) {
if (head.val != newHead.val) return false;
head = head.next;
newHead = newHead.next;
}
return true;
}
//反转链表函数--详情请看前文
private ListNode reverseList(ListNode head) {
if (head.next == null) return head;
ListNode pre = null;
ListNode tmp;
while (head!= null) {
tmp = head.next;//tmp暂存当前节点的下一个节点
head.next = pre;//当前节点下一个指向pre
pre = head;//刷新pre
head = tmp;//刷新当前节点为tmp
}
return pre;
}
}