回文链表

Leetcode Link: 234. 回文链表 - 力扣（LeetCode） (leetcode-cn.com)

题目

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

解法一

思路：栈，先遍历一次将值入栈，在遍历一次逐一比较。

题解：时间复杂度 $O(N)$，额外空间复杂度$O(N)$

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        ## 栈方法
        sList = []
        cur = head
        # 节点值一个一个进栈
        while(cur):
            sList.append(cur.val)
            cur = cur.next
        # 逐一对比
        cur = head
        for val in sList[::-1]:
            if val != cur.val:
                return False
            cur = cur.next
        return True

解法二

思路：双指针，快指针走两步，慢指针走一步。快指针走到末尾，则慢指针到中点位置；之后将后半部分连边翻转；再两边往中间走对比节点value

题解：时间复杂度$O(N)$，额外空间复杂度$O(1)$?

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        ## 双指针
        fast = head
        slow = head
        # slow指针找到中点（注意这里的两个判断其实暗含了奇偶性）
        while(fast.next):
            if fast.next.next!= None:
                fast = fast.next.next
            else:
                fast = fast.next
            slow = slow.next
        # 反转链表，fast从头
        fast = head
        slow = self.reverseNode(slow)
        # 两边往中间比较
        # 对于奇数个节点（中间剩一个那种），下面的写法可以忽略中间那个
        while(slow != None and fast != None):
            if slow.val != fast.val:
                return False
            slow = slow.next
            fast = fast.next
        # 这里没有把原来的链表翻转回来，因为本题不需要。
        return True
    
    def reverseNode(self, head1:ListNode) -> ListNode:
        curNode = head1
        lastNode = None
        while(curNode):
            nextNode = curNode.next
            curNode.next = lastNode
            lastNode = curNode
            curNode = nextNode
        return lastNode

本解法部分参考了解法二

解法三

思路：递归。即反向返回链表节点的值，然后和正向的值一一比较。

题解：

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        ## 递归
        self.head = head
        self.flag = 1
        a = self.reverseReturnList(head)
        if self.flag == 0:
            return False
        else:
            return True
 
    # 反向返回链表值的方法
    def reverseReturnList(self, curNode):
        if curNode.next == None:
           return curNode.val
        else:
            value = self.reverseReturnList(curNode.next)
            if self.head.val != value:
                self.flag = 0
            self.head = self.head.next
            return curNode.val

解法三的缺点

慢且额外空间大，需要全部跑完才能返回True和False，不能一半就返回

代码优化

代码可以进一步优化，但是比较难想，我没有进一步优化。可以参考这里)

启发和联系