这篇文章给大家分享的是有关LeetCode如何判断回文链表的内容。小编觉得挺实用的，因此分享给大家做个参考，一起跟随小编过来看看吧。
请判断一个链表是否为回文链表。
输入: 1->2输出: false
输入: 1->2->2->1输出: true
避免使用 O(n)O(n) 额外空间的方法就是改变输入。
我们可以将链表的前（后）半部分反转（修改链表结构），然后将前半部分和后半部分进行比较。比较完成后我们应该将链表恢复原样。虽然不需要恢复也能通过测试用例，但是使用该函数的人通常不希望链表结构被更改。
该方法虽然可以将空间复杂度降到 O(1)O(1)，但是在并发环境下，该方法也有缺点。在并发环境下，函数运行时需要锁定其他线程或进程对链表的访问，因为在函数执行过程中链表会被修改。
整个流程可以分为以下步骤：
找到前（后）半部分链表的尾节点。
反转（前）后半部分链表。
判断是否回文。
计算
安全
数据库
网络和加速
企业服务
# Definition for singly-linked list.# class ListNode:# def __init__(self, x):# self.val = x# self.next = Noneclass 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/** * 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。
算法的正确性在于递归处理节点的顺序是相反的，而我们在函数外又记录了一个变量，因此从本质上，我们同时在正向和逆向迭代匹配。
所谓递归，即从上往下递下去，然后再从下往上归回来。
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如何判断回文链表”这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，让大家可以学到更多知识，如果觉得文章不错，可以把它分享出去让更多的人看到吧！
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
原文链接：https://my.oschina.net/u/4597666/blog/4935572
