LeetCode如何判断回文链表
这篇文章给大家分享的是有关LeetCode如何判断回文链表的内容。小编觉得挺实用的,因此分享给大家做个参考,一起跟随小编过来看看吧。
题目描述:
请判断一个链表是否为回文链表。
示例 1:
输入: 1->2输出: false
示例 2:
输入: 1->2->2->1输出: true
思路分析:
迭代法:
避免使用 O(n)O(n) 额外空间的方法就是改变输入。
我们可以将链表的前(后)半部分反转(修改链表结构),然后将前半部分和后半部分进行比较。比较完成后我们应该将链表恢复原样。虽然不需要恢复也能通过测试用例,但是使用该函数的人通常不希望链表结构被更改。
该方法虽然可以将空间复杂度降到 O(1)O(1),但是在并发环境下,该方法也有缺点。在并发环境下,函数运行时需要锁定其他线程或进程对链表的访问,因为在函数执行过程中链表会被修改。
整个流程可以分为以下步骤:
找到前(后)半部分链表的尾节点。
反转(前)后半部分链表。
判断是否回文。
Python实现
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def isPalindrome(self, head):
"""
:type head: ListNode
:rtype: bool
"""
if head is None or head.next is None:
return True
if head.next.next is None:
return head.val == head.next.val
fast = slow = q = head
while fast.next and fast.next.next:#这里快指针的判读条件跟判断环形有一点不同
fast = fast.next.next
slow = slow.next
def reverse_list(head):
if head is None:
return head
cur = head
pre = None
nxt = cur.next
while nxt:
cur.next = pre
pre = cur
cur = nxt
nxt = nxt.next
cur.next = pre
return cur
p = reverse_list(slow.next)
while p.next:
if p.val != q.val:
return False
p = p.next
q = q.next
return p.val == q.val
java实现:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
if(head == null || head.next == null) {
return true;
}
ListNode slow=head;
ListNode fast=head;
ListNode pre=null,prepre=null;
//反转前半部分指针
while(fast!=null&&fast.next!=null){
pre=slow;
slow=slow.next;
fast=fast.next.next;
pre.next=prepre;
prepre=pre;
}
if(fast != null) {
slow = slow.next;
}
//比较前后部分指针是否相同
while(pre!=null&&slow!=null){
if(pre.val!=slow.val){
return false;
}
pre=pre.next;
slow=slow.next;
}
return true;
}
}
递归法:
currentNode 指针是先到尾节点,由于递归的特性再从后往前进行比较。frontPointer 是递归函数外的指针。若 currentNode.val != frontPointer.val 则返回 false。反之,frontPointer 向前移动并返回 true。
算法的正确性在于递归处理节点的顺序是相反的,而我们在函数外又记录了一个变量,因此从本质上,我们同时在正向和逆向迭代匹配。
所谓递归,即从上往下递下去,然后再从下往上归回来。
java实现代码:
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);
}
感谢各位的阅读!关于“LeetCode如何判断回文链表”这篇文章就分享到这里了,希望以上内容可以对大家有一定的帮助,让大家可以学到更多知识,如果觉得文章不错,可以把它分享出去让更多的人看到吧!