LeetCode: 234 Palindrome Linked List

Given the head of a singly linked list, return true if it is a palindrome.

Example

Input: head = [1,2,2,1]
Output: true

Input: head = [1,2]
Output: false

问题

给定单链表的头节点 head，如果它是回文链表，则返回 true。

例子

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

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

Solution

Approach: Two Pointers (Fast and Slow) / 双指针法（快慢指针）

To determine if a linked list is a palindrome, we can use the two-pointer technique. First, use fast and slow pointers to find the middle of the linked list. Then, reverse the second half of the list and compare it with the first half to check if the list is a palindrome.

Approach Explanation

Find Middle: Use two pointers (slow and fast) to locate the middle of the list.
Reverse the Second Half: Reverse the second half of the list starting from the middle.
Compare Halves: Compare the first half and the reversed second half node by node.

Step-by-Step Process

Move Fast and Slow Pointers: Move fast by two steps and slow by one step to find the middle.
Reverse Second Half: Reverse the list starting from the slow pointer.
Compare: Compare the values from the first half (starting from head) and the second half (starting from the reversed list).

Implementation

Python

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        if not head or not head.next:
            return True

        # Step 1: Find the middle of the list
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        # Step 2: Reverse the second half of the list
        prev = None
        while slow:
            next_node = slow.next
            slow.next = prev
            prev = slow
            slow = next_node

        # Step 3: Compare the first half and the reversed second half
        left, right = head, prev
        while right:  # Only need to compare till the end of the reversed half
            if left.val != right.val:
                return False
            left = left.next
            right = right.next

        return True

Explanation

Handle Edge Cases / 处理特殊情况
```
if not head or not head.next:
   return True
```
- English: If the list has one or no elements, it’s a palindrome by definition.
- Chinese: 如果链表只有一个或没有元素，那么它本身就是回文链表。
Find the Middle of the List / 找到链表的中点
```
slow, fast = head, head
while fast and fast.next:
   slow = slow.next
   fast = fast.next.next
```
- English: We use the fast and slow pointers to find the middle of the list. The fast pointer moves twice as fast as the slow pointer.
- Chinese: 我们使用快慢指针找到链表的中点。快指针每次移动两步，慢指针每次移动一步。
Reverse the Second Half / 反转链表的后半部分
```
prev = None
while slow:
   next_node = slow.next
   slow.next = prev
   prev = slow
   slow = next_node
```
- English: Starting from the middle, reverse the second half of the linked list.
- Chinese: 从中点开始，反转链表的后半部分。
Compare Two Halves / 比较链表的前半部分和反转后的后半部分
```
left, right = head, prev
while right:
   if left.val != right.val:
       return False
   left = left.next
   right = right.next
```
- English: Compare the first half and the reversed second half node by node. If they don’t match at any point, return False.
- Chinese: 逐个比较链表的前半部分和反转后的后半部分。如果任何一个节点不匹配，返回 False。
Return Result / 返回结果
```
return True
```
- English: If all nodes match, the list is a palindrome, so return True.
- Chinese: 如果所有节点都匹配，则链表是回文链表，返回 True。

Complexity Analysis

Time Complexity / 时间复杂度: O(n), where n is the number of nodes in the list. We traverse the list a couple of times (to find the middle, reverse the second half, and compare both halves).
Space Complexity / 空间复杂度: O(1), since we only use a few pointers and no additional data structures.

Key Concept

Two Pointers / 双指针: The fast and slow pointer technique helps find the middle of the list efficiently.
Reversing a List / 反转链表: Reversing part of a list is a key operation to make the comparison between the two halves.

Summary

English: We solve this problem by using two pointers to find the middle of the list, reversing the second half, and then comparing both halves to check if the list is a palindrome.
Chinese: 通过使用双指针找到链表的中点，反转后半部分，然后比较前后两部分，来检查链表是否为回文链表。

Tips

English: Practice problems involving linked list traversal and in-place modifications to become comfortable with techniques like two-pointer and reversing a linked list.
Chinese: 练习涉及链表遍历和原地修改的问题，以熟悉双指针和反转链表等技术。

5 More Similar Questions

Recommended Resources

English: Practice problems involving linked lists, especially those involving in-place modification and two-pointer techniques.
Chinese: 练习涉及链表的问题，特别是涉及原地修改和双指针技术的题目。

Palindrome Linked List – Leetcode 234 – Python by NeetCode

Post Views: 13

CODEBITWAVE