LeetCode 234：回文链表 Palindrome Linked List

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

Given a singly ed list, determine if it is a palindrome.

示例 1:

输入: 1->2输出: false

示例 2:

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

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

Follow up:
Could you do it in O(n) time and O(1) space?

解题思路：

首先是寻找链表中间节点，这个可以用快慢指针来解决，快指针速度为2，慢指针速度为1，快指针遍历完链表时，慢指针刚好走到中间节点（相对）。

然后是判断是否是回文链表：

不考虑进阶要求的话，方法千千万。可以把前半部分暂存入新的数组、链表、哈希表等等数据结构，然后依次倒序取出，与后半部分链表每个节点的值对比即可。更简单的是直接用数据结构 - 栈，先进后出，把节点压入栈中，到中间节点后，依次从栈中弹出节点，与后半部分的节点值对比即可。

直接思考进阶要求，在 O(1) 的空间复杂度下，只能选择操作原链表来完成该题。好在这道题只要求返回布尔值，即便把原链表改变了也不用担心。我们可以将链表后半部分 反转，利用迭代法反转链表，时间复杂度为 O(n),空间复杂度为 O(1)，所以符合要求。然后从原链表头节点 与 反转后后半部分链表头节点开始对比值即可。

反转链表的各种详细方法在前几日的那道题中已经详细解答过，未看过的朋友可以先看那一篇：LeetCode 206：反转链表 Reverse ed List

Java：

class Solution {    public boolean isPalindrome(ListNode head) {        ListNode fast = head;        ListNode slow = head;        if (fast == null || fast.next == null) return true;        while (fast.next != null && fast.next.next != null) {            fast = fast.next.next;            slow = slow.next;        }        ListNode newHead = reverseList(slow.next);        while (newHead != null) {            if (head.val != newHead.val) return false;            head = head.next;            newHead = newHead.next;        }        return true;    }    //反转链表函数--详情请看前文    private ListNode reverseList(ListNode head) {        if (head.next == null) return head;        ListNode pre = null;        ListNode tmp;        while (head!= null) {            tmp = head.next;//tmp暂存当前节点的下一个节点            head.next = pre;//当前节点下一个指向pre            pre = head;//刷新pre            head = tmp;//刷新当前节点为tmp        }        return pre;    }}

Python：

class Solution:    def isPalindrome(self, head: ListNode) -> bool:        fast, slow = head, head        if not fast or not fast.next: return True        while fast.next and fast.next.next:            fast = fast.next.next            slow = slow.next        newHead = self.reverseList(slow.next)        while newHead:            if newHead.val != head.val: return False            newHead = newHead.next            head = head.next        return True    def reverseList(self, head: ListNode) -> ListNode:        if not head or not head.next:            return head        pre, tmp = None, None        while (head):            tmp = head.next            head.next = pre            pre = head            head = tmp        return pre

欢迎关注公.众号一起学习: 爱写Bug