当前位置 博文首页 > 知北行的博客：算法--- LeetCode 234. 回文链表
原题链接
请判断一个链表是否为回文链表。
示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true
进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
Related Topics 链表 双指针
👍 802 👎 0
题解1:
/**
* 解法 1 :
* 遍历一遍链表并存储到数组中,
* 然后使用双指针法判断数组是否为回文
*/
class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null) {
return true;
}
ArrayList<Integer> list = new ArrayList<>();
while (head != null) {
list.add(head.val);
head = head.next;
}
int size = list.size();
int i = 0, j = size - 1;
while (i < j) {
if (!list.get(i).equals(list.get(j))) {
return false;
}
i++;
j--;
}
return true;
}
}
题解 2:
/**
* 解法 2:
* 1. 使用快慢指针寻找链表中点
* 2. 翻转后半部分链表
* 3. 判断链表是否回文
* 4. 恢复链表
*/
class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null) {
return true;
}
ListNode firstEnd = findMid(head);
ListNode secondStart = reverseList(firstEnd.next);
boolean result = true;
ListNode p = head, q = secondStart;
// 注意这里 q 可能为 null ,需要在循环体中判断
while (p != q && q!=null) {
if (p.val != q.val) {
result = false;
break;
}
p = p.next;
q = q.next;
}
// 恢复链表
firstEnd.next = reverseList(secondStart);
return result;
}
// 发现中间节点
public ListNode findMid(ListNode head) {
if (head == null) {
return null;
}
ListNode fast = head, slow = head;
while (fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
// 反转链表, 这里注意从 null 开始翻转
public ListNode reverseList(ListNode head) {
if (head == null) {
return null;
}
ListNode pre = null, p = head;
while (p != null) {
ListNode temp = p.next;
p.next = pre;
pre = p;
p = temp;
}
return pre;
}
}
