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

题目描述

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

示例 1:

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

示例 2:

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

提示:

  • 链表中节点数目在范围[1, 105] 内
  • 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函数反转中间节点后面的链表。
    • 使用两个指针p1p2从链表头部和中间开始对比节点值。
    • 判断条件是p2 != nil ,因为如果链表节点数是单数,p1会多一个节点,多的这个节点是中间节点,不用判断
    • 如果存在不同的节点值,返回false
    • 最后,恢复原链表结构并返回true
  2. reverseList函数:这个函数用于反转一个链表。

    • 初始化prenil
    • 使用cur遍历原链表,cur指向当前遍历到的节点。
    • 在循环中,首先保存cur的下一个节点到next
    • curNext指针指向pre,这一步是实现反转的关键。
    • 然后移动precur,将cur移到下一个节点。
    • 循环直到curnil,表示原链表已经遍历完。
    • 返回pre,即新的头节点。
  3. midPoint函数:这个函数用于找到链表的中间节点。

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

相关推荐

  1. LeetCode-100:234.

    2024-04-03 23:46:02       6 阅读
  2. leetcode-

    2024-04-03 23:46:02       24 阅读
  3. leetcode 234

    2024-04-03 23:46:02       22 阅读
  4. leetcodeHOT leetcode131. 分割

    2024-04-03 23:46:02       11 阅读
  5. LeetCode 100 | (下)

    2024-04-03 23:46:02       23 阅读

最近更新

  1. 11-3.Vue2.x基本列表—列表排序—sort

    2024-04-03 23:46:02       0 阅读
  2. spring注解整理

    2024-04-03 23:46:02       0 阅读
  3. Qt 实战(1)Qt 概述

    2024-04-03 23:46:02       0 阅读
  4. Qt——选中所有的RadioButton

    2024-04-03 23:46:02       0 阅读
  5. 设计模式-策略模式

    2024-04-03 23:46:02       0 阅读

热门阅读

  1. C++(12): std::mutex及其高级变种的使用

    2024-04-03 23:46:02       4 阅读
  2. YOLO_Tracking 实践 (环境搭建 & 案例测试)

    2024-04-03 23:46:02       4 阅读
  3. sqlmap基础知识(二)

    2024-04-03 23:46:02       4 阅读
  4. 【NC201605】Bits

    2024-04-03 23:46:02       5 阅读
  5. 算法刷题记录 Day35

    2024-04-03 23:46:02       4 阅读
  6. VC++、GCC、CLANG,INT128有符号整数编译器关键字

    2024-04-03 23:46:02       4 阅读
  7. Python 抽象类

    2024-04-03 23:46:02       6 阅读
  8. 第六章:使用 kubectl 创建 Deployment

    2024-04-03 23:46:02       4 阅读
  9. vue3 + howuse, 实现echarts symbol使用 gif 动画图片

    2024-04-03 23:46:02       4 阅读
  10. 初识人工智能---------自然语言处理&&词袋模型

    2024-04-03 23:46:02       6 阅读