[力扣题解]：234. 回文链表

题目要求

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

示例 1:

输入: 1->2

输出: false

示例 2:

输入: 1->2->2->1

输出: true

进阶：

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

解题思路

• 寻找回文串要从中间向两侧延伸，判断回文串则要从两端向中间遍历

1.双指针判断回文字符串

• 字符串为数组型顺序存储，可快速索引到字符串两端，故采用双指针

def isPalindrome(s):
    left = 0
    right =len(s)-1
    while (left < right) :
        if (s[left] != s[right])
            return false;
        left+=1
        right-=1
    return true

           

2.单链表的反向遍历

• 显然，只要可以实现单链表的反向遍历，便可实现和双指针相似的效果
• 最简单办法是由反转链表将反转后的链表存入数组或新的链表，也可以利用递归

def traverse(head):
    if head == None:
    	return
    traverse(head.next)
    // 后序遍历代码
    print(head.val)

           

3.判断回文串

• 稍作修改便可实现

def traverse(right):
    if right== None:
    	return True
    res=traverse(right.next) and (left.val==right.val)
    left=left.next
    return res
    	
def isPalindrome(head):
    left = head
    return traverse(head)
           

4.进阶

• 虽然我们实现了判断回文串，但由于递归操作实际上是堆栈操作，空间复杂度为O(n)，故需要采取其他方式降低空间复杂度

a.快慢指针找到中间节点

slow=head
fast=head
if(fast and fast.next):
	slow=slow.next
	fast=fast.next.next
           

• 若长度为奇数，则增加一步操作

if fast:
	slow=slow.next
           

b.反转中间节点后的链表

• 利用反转链表我们就可以得到两端的指针

  

c.从两端向中间遍历

• 至此，结合以上三步，便可降低空间复杂度为O(n)

def isPalindrome(head: ListNode) -> bool:
        if head.next==None:
            return True
        slow=head
        fast=head
        left=head
        if (fast and fast.next):
            slow=slow.next
            fast=fast.next.next
        if fast!=None:
            slow=slow.next
        right=reverse(slow)
        while(right!=None and left!=None):
            if right.val!=left.val:
                return False
            right=right.next
            left=left.next
        return True
    def reverse(head):
        if head==None:
            return head
        if head.next==None:
            return head
        last=reverse(head.next)
        head.next.next=head
        head.next=None
        return last
           

参考资料

labuladong的算法小抄

234. 回文链表 - 力扣