LeetCode笔记：234. Palindrome Linked List
LeetCode笔记：234. Palindrome Linked List
Cloudox
发布于 2021-11-23 14:59:45
发布于 2021-11-23 14:59:45
问题：
Given a singly linked list, determine if it is a palindrome. Follow up: Could you do it in O(n) time and O(1) space?
大意：
给出一个单链表，判断它是否是回文。 进阶： 你能在O（n）的时间复杂度和O（1）的空间复杂度下来做吗？
思路：
回文的意思就是正着读反着读都是一样的。
这道题我使用简单的思路，一个个遍历链表节点来倒序组成一个新链表，然后和旧链表一起遍历看节点是不是一样的，如果一样说明是回文，否则不是。这个方法很简单，时间复杂度是O（n），但是空间复杂度也是O（n），并不符合进阶的要求。
代码（Java）：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) return true;
ListNode newHead = head;
ListNode lastNode = new ListNode(head.val);
while (newHead.next != null) {
newHead = newHead.next;
ListNode newNode = new ListNode(newHead.val);
newNode.next = lastNode;
lastNode = newNode;
}
if (head.val != lastNode.val) return false;
while (head.next != null) {
head = head.next;
lastNode = lastNode.next;
if (head.val != lastNode.val) return false;
}
return true;
}
}他山之石：
public class Solution {
public boolean isPalindrome(ListNode head) {
ListNode fast = head, slow = head;
Stack<ListNode> stack = new Stack<>();
while(fast != null && fast.next != null){
stack.push(slow);
fast = fast.next.next;
slow = slow.next;
}
// for odd list
if(fast != null){
slow = slow.next;
}
while(slow != null){
if(stack.pop().val != slow.val) return false;
slow = slow.next;
}
return true;
}
}这个做法跟我的不一样，使用了快慢两个标记，快的那个只有一个用处，就是以两倍速度遍历，引导慢的标记到达链表最中心，当然这里要根据链表个数是奇数还是偶数来分开判断，也是看fast是正好跑到最后面还是跑过了来判断。找到中心后，利用栈存放的数据先进后出的特性，从中间往两头一起遍历，看遍历的值是不是都一样，一样则是回文，否则不是。这个做法同样的时间复杂度是O（n），二空间复杂度是O（n），因为用到了一个栈。不过速度应该比我的要快一半
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2017/11/22 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录