LeetCode 234. 回文链表

文章目录

• 前言
• 题目
• 题解
• NO1：复制数组+双指针
• NO2：反转链表+双指针
• 参考文章

前言

哈喽，我是长路，目前刚刚大三，方向是后端也偶尔捣鼓下前端，现在的主语言是Java。之前一大段时间都是在学习web开发的一些技术，就很久没有进行类似于数据结构、算法之类的学习与刷题，打算这段时间拾起来好好学一学、搞一搞。

这段时间也是机缘巧合看到草帽路飞的博客，加了自学群，正巧看到博主组织在群里组织了leetcode刷题打卡活动，我也就参与进来，为期一个月，打算坚持每天都花一些时间做一些题目，并通过博客的方式来进行记录。

目前跟着一个Github仓库刷题(leetcode)：代码随想录leetcode刷题，当前为LeetCode 热题 HOT 100专题。

---

题目

题目来源leetcode

leetcode地址：234. 回文链表，难度：简单。

题目描述(摘自leetcode)：

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
示例 1：
输入：head = [1,2,2,1]
输出：true

示例 2：
输入：head = [1,2]
输出：false
 
提示：
链表中节点数目在范围[1, 105] 内
0 <= Node.val <= 9

---

题解

NO1：复制数组+双指针

思路：先将链表中的值进行拷贝到数组中去，接着对数组从左右两边依次进行比对即可！

代码：时间复杂度O(n)，空间复杂度O(n)

class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head.next == null){
            return true;
        }
        //将链表中的值转为数组
        List<Integer> nodes = new ArrayList<>();
        while(head != null){
            nodes.add(head.val);
            head = head.next;
        }
        //分别从后往前依次比对
        int left = 0;
        int right = nodes.size() - 1;
        while(left < right){
            if (nodes.get(left) != nodes.get(right)){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

leetcode运行截图

---

NO2：反转链表+双指针

思路：使用快慢指针来决定链表反转的部分，也就是链表的前一半。反转链表的前一半部分节点，接着从之间两边开始一同出发进行比对。

代码：时间复杂度O(n)，空间复杂度O(1)

public boolean isPalindrome(ListNode head) {
    //反转前面一半节点
    ListNode slow = head,fast = head;
    ListNode pre = null;
    ListNode cur = head;
    while (fast != null && fast.next != null){
        slow = slow.next;
        fast = fast.next.next;
        //进行反转链表
        cur.next = pre;
        pre = cur;
        cur = slow;
    }
    //链表长度为奇数个
    if (fast != null){
        slow = slow.next;
    }

    //开始从pre、slow开始比对
    while(pre != null){
        if (pre.val != slow.val){
            return false;
        }
        pre = pre.next;
        slow = slow.next;
    }
    return true;
}

---

参考文章

[1]. leetcode题解

[2]. 反转链表+双指针题解

---

我是长路，感谢你的耐心阅读。如有问题请指出，我会积极采纳！ 欢迎关注我的公众号【长路Java】，分享Java学习文章及相关资料 Q群：851968786 我们可以一起探讨学习 注明：转载可，需要附带上文章链接

整理者：长路 时间：2021.11.12