当前位置: 首页 > >

LeetCode 234. 回文链表

发布时间:

目录结构

1.题目


2.题解


2.1辅助数组


2.2链表部分反转



1.题目

请判断一个链表是否为回文链表。


示例:


输入: 1->2
输出: false


输入: 1->2->2->1
输出: true

进阶:
你能否用?O(n) 时间复杂度和 O(1) 空间复杂度解决此题??



来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/palindrome-linked-list
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。



2.题解
2.1辅助数组

使用数组存储链表的元素,然后设置前后双指针遍历数组并判定。


public class Solution234 {
public boolean isPalindrome(ListNode head) {
List list = new ArrayList<>();
while (head != null) {
list.add(head.val);
head = head.next;
}
int front = 0, back = list.size() - 1;
while (front < back) {
if (!list.get(front).equals(list.get(back))) {
return false;
}
front++;
back--;
}
return true;
}
}

时间复杂度:空间复杂度:
2.2链表部分反转

r指针记录后半部分开始节点的前一个节点,便于还原链表。


找到前半部分链表的尾节点;反转后半部分链表;判断是否为回文;恢复链表;返回结果。

public class Solution234 {
public boolean isPalindrome(ListNode head) {
if (head == null) {
return true;
}
ListNode p = head, q, r = null;
int count = 0, flag = 1;
while (p != null) {
count++;
p = p.next;
}
if (count == 1){
return true;
}
count = count % 2 == 0 ? count / 2 : count / 2 + 1;
p = head;
while (count != 0) {
if (count == 1) {
r = p;
}
p = p.next;
count--;
}
q = reverse(p);
p = head;
while (q != null) {
if (q.val != p.val) {
flag = 0;
break;
}
q = q.next;
p = p.next;
}
r.next = reverse(p);
return flag == 1;
}

public ListNode reverse(ListNode head) {
ListNode p = null, tmp;
while (head != null) {
tmp = head.next;
head.next = p;
p = head;
head = tmp;
}
return p;
}
}

时间复杂度:空间复杂度:



友情链接: