234.回文链表

• 题目
• 法一、复制+反转链表
• 法二、堆栈
• 法三、快慢指针和链表反转

题目

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

示例 1：

输入：head = [1,2,2,1]
输出：true

示例 2：

输入：head = [1,2]
输出：false

法一、复制+反转链表

• 把原链表翻转一下，与没翻转的链表对比，相同则是回文，返回True，不同则返回False。在进行链表翻转时需要把原链表节点一个一个取下来，用头插法放到新的链表中，导致原链表被拆毁，没法比较了，所以一开始先把原链表复制一份。

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        if not head or not head.next:#空链表和单个节点链表
            return True

        # 复制链表
        new_head = ListNode(0)#定义复制链表的头节点
        new_current = new_head
        current = head

        while current:#当原链表没到链尾时进行复制
            new_node = ListNode(current.val)#创建一个新的节点，把原链表当前指针所指的值赋与
            new_current.next = new_node#把这个节点加载在新链表
            new_current = new_current.next#新链表的当前指针后移
            current = current.next#原链表的指针后移

        # 反转链表
        new_head2 = ListNode(0)#定义反转链表的头节点
        pre = head#pre指针指向头
        while pre:#当pre没到链表结尾时循环
            cur = pre.next#把pre的下一个指针赋给指针cur
            pre.next = new_head2.next#把新的头节点的next赋给pre的next
            new_head2.next = pre#新的头节点的next指向pre
            pre = cur#更新pre

        # 比较链表是否回文
        i, j = new_head.next, new_head2.next
        while i and j:
            if i.val != j.val:
                return False
            i = i.next
            j = j.next
        return True

• 时间复杂度为 O(n)，空间复杂度为 O(n)

法二、堆栈

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        stack = []#创建一个空栈 stack 用于存储链表节点
        # step1: push 
        curr = head
        while(curr):#遍历链表
            stack.append(curr)#将节点依次压入栈中
            curr = curr.next
        # step2: pop and compare
        node1 = head#链表的当前节点 node1 
        while(stack):
            node2 = stack.pop()#弹出的栈顶元素
            if node1.val != node2.val:
                return False
            node1 = node1.next
        return True

• 时间复杂度为 O(n)，空间复杂度为 O(n)

法三、快慢指针和链表反转

1.使用快慢指针找到链表的中间节点。快指针每次移动两步，慢指针每次移动一步，当快指针到达链表末尾时，慢指针指向的节点即为链表的中间节点。
2.反转链表的后半部分。从中间节点开始，将后半部分链表进行反转操作。
3.比较链表的前半部分和反转后的后半部分。分别使用两个指针同时遍历两部分链表，比较节点的值是否相等。如果所有节点的值都相等，则链表是回文的；否则，链表不是回文的。
4.恢复链表并返回结果。将反转后的后半部分链表再次进行反转操作，使链表恢复原来的顺序。

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        if not head or not head.next:#空链表和单个节点链表
            return True

        # 找到链表的中间节点
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        # 反转后半部分链表
        prev = None
        while slow:
            next_node = slow.next
            slow.next = prev
            prev = slow
            slow = next_node

        # 比较链表的前半部分和反转后的后半部分
        p1, p2 = head, prev
        while p1 and p2:
            if p1.val != p2.val:
                return False
            p1 = p1.next
            p2 = p2.next

        # 恢复链表
        prev = None
        while prev != None:
            next_node = p2.next
            p2.next = prev
            prev = p2
            p2 = next_node

        return True

• 时间复杂度为 O(n)，空间复杂度为 O(1)