LeetCode-热题100：234. 回文链表

题目描述

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

示例 1：

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

示例 2：

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

提示：

• 链表中节点数目在范围[1, 10⁵] 内
• 0 <= Node.val <= 9

代码及注释

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

// 判断一个链表是否为回文链表
func isPalindrome(head *ListNode) bool {
    // 如果链表为空，直接返回true
    if head == nil {
        return true
    }

    // 找到链表的中间节点
    middle := midPoint(head)
    // 反转中间节点后面的链表
    reverseMiddle := reverseList(middle.Next)
    // 从头部和中间开始对比链表节点值
    p1, p2 := head, reverseMiddle
    // 判断条件是p2 != nil ，因为如果链表节点是单数，p1会多一个节点，多的这个节点是中间节点，不用判断
    for p2 != nil {
        if p1.Val != p2.Val {
            return false
        }
        p1 = p1.Next
        p2 = p2.Next
    }
    // 恢复原链表结构
    middle.Next = reverseList(reverseMiddle)
    return true
}

// 反转链表
func reverseList(head *ListNode) *ListNode {
    var pre *ListNode
    cur := head
    // 循环遍历链表
    for cur != nil {
        // 保存当前节点的下一个节点
        next := cur.Next
        // 将当前节点的Next指针指向pre
        cur.Next = pre
        // pre和cur节点都向前移动一位
        pre = cur
        cur = next
    }
    return pre
}

// 寻找链表的中间节点
func midPoint(head *ListNode) *ListNode {
    slow, fast := head, head
    // 使用快慢指针找到链表的中间节点
    for fast.Next != nil && fast.Next.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
    }
    return slow
}

代码解释

1. isPalindrome函数：这个函数用于判断给定的链表是否为回文链表。

   • 如果链表为空，直接返回true。
   • 使用midPoint函数找到链表的中间节点。
   • 使用reverseList函数反转中间节点后面的链表。
   • 使用两个指针p1和p2从链表头部和中间开始对比节点值。
   • 判断条件是p2 != nil ，因为如果链表节点数是单数，p1会多一个节点，多的这个节点是中间节点，不用判断
   • 如果存在不同的节点值，返回false。
   • 最后，恢复原链表结构并返回true。

2. reverseList函数：这个函数用于反转一个链表。

   • 初始化pre为nil。
   • 使用cur遍历原链表，cur指向当前遍历到的节点。
   • 在循环中，首先保存cur的下一个节点到next。
   • 将cur的Next指针指向pre，这一步是实现反转的关键。
   • 然后移动pre和cur，将cur移到下一个节点。
   • 循环直到cur为nil，表示原链表已经遍历完。
   • 返回pre，即新的头节点。

3. midPoint函数：这个函数用于找到链表的中间节点。

   • 使用快慢指针slow和fast遍历链表。
   • fast每次移动两步，slow每次移动一步。
   • 当fast到达链表的末尾时，slow指向的就是中间节点。