高频算法题-回文链表
2023-03-07 09:49:51 时间
https://leetcode.cn/problems/palindrome-linked-list/
解法一:
时间复杂度:O(n),其中 n 指的是链表的元素个数。
- 第一步:遍历链表并将值复制到数组中,O(n)。
- 第二步:双指针判断是否为回文,执行了 O(n/2) 次的判断,即 O(n)。
总的时间复杂度:O(n)。
空间复杂度:O(n),其中 n 指的是链表的元素个数,我们使用了一个数组列表存放链表的元素值。
class Solution {
public boolean isPalindrome(ListNode head) {
List<Integer> vals = new ArrayList<Integer>();
// 将链表的值复制到数组中
ListNode currentNode = head;
while (currentNode != null) {
vals.add(currentNode.val);
currentNode = currentNode.next;
}
// 使用双指针判断是否回文
int front = 0;
int back = vals.size() - 1;
while (front < back) {
if (!vals.get(front).equals(vals.get(back))) {
return false;
}
front++;
back--;
}
return true;
}
}
解法二:
时间复杂度:O(n),其中 nn 指的是链表的大小。
空间复杂度:O(1)。我们只会修改原本链表中节点的指向,而在堆栈上的堆栈帧不超过 O(1)。
class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null) {
return true;
}
// 找到前半部分链表的尾节点并反转后半部分链表
ListNode firstHalfEnd = endOfFirstHalf(head);
ListNode secondHalfStart = reverseList(firstHalfEnd.next);
// 判断是否回文
ListNode p1 = head;
ListNode p2 = secondHalfStart;
boolean result = true;
while (result && p2 != null) {
if (p1.val != p2.val) {
result = false;
}
p1 = p1.next;
p2 = p2.next;
}
// 还原链表并返回结果
firstHalfEnd.next = reverseList(secondHalfStart);
return result;
}
private ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
private ListNode endOfFirstHalf(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
}
解法三:
- 时间复杂度:O(n)其中 n )指的是链表的大小。
- 空间复杂度:)O(n),其中 nn 指的是链表的大小。
class Solution {
private ListNode frontPointer;
private boolean recursivelyCheck(ListNode currentNode) {
if (currentNode != null) {
if (!recursivelyCheck(currentNode.next)) {
return false;
}
if (currentNode.val != frontPointer.val) {
return false;
}
frontPointer = frontPointer.next;
}
return true;
}
public boolean isPalindrome(ListNode head) {
frontPointer = head;
return recursivelyCheck(head);
}
}
相关文章
- CSS 01 准备 选择器、伪元素
- CSS 02 border-radius
- CSS 03 线性渐变、径向渐变与重复性渐变
- CSS 04 盒子阴影效果box-shadow
- CSS 05 transition特效
- CSS 06 动画
- CSS 07 文字处理
- arcgis api 3.X 修改自带弹窗样式 2022年6月12日
- 2023-02-13:力扣数据中心有 n 台服务器,分别按从 0 到 n-1 的方式进行了编号 它们之间以「服务器到服务器」点对点的形式相互连接组成了一个内部集
- 机器学习算法:随机森林
- R语言Pearson相关性分析就业率和“性别平等”谷歌搜索热度google trend时间序列数据可视化
- 截断数组
- 脚手架soothboot
- JavaWeb day1 html快速入门
- ChatGPT这波热潮会不会让我失业?
- Camtasia2023最新版使用快捷键教程
- 33复杂美:一文看懂加密算法为何物
- dotnet 8 preview 1 即将发布
- 这家脑机接口公司在美国实现了重要的里程碑
- 一种具有神经形态硬件解码器的双向脑机接口