重温算法之回文链表

简介: 双指针法确实在很多算法题里都遇到了,其用法很普遍,掌握起来也不难,还有就是回文系列的题目都有共通点,做多了就明白里面的

微信截图_20220531173728.png

一.题目介绍


1.题目来源


链接:LeetCode


2.题目


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

示例 1:

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

输出:true

示例 2:

输入:head = [1,2]

输出:false

 提示:

链表中节点数目在范围[1, 105]内

0 <= Node.val <= 9


二.具体实现


1.实现思路

判断是否是回文链表,第一步是需要找到中间节点,并且翻转前边节点,然后依次判断值是否相同,其思路跟做回文子串的基本相同,或者说这个回文系列的题目的思路按这种方法都能解决,下面看看具体实现。


2.实现代码


1)自己的实现方式

public boolean isPalindrome(ListNode head) {
    if (head == null || head.next == null) {
        return true;
    }
    //找到中节点
    ListNode fast = head;
    ListNode slow = head;
    while (fast.next != null && fast.next.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    //此时slow就是前半部分,翻转后半部分
    ListNode pre = null;
    ListNode cur = slow.next;
    while (cur != null) {
        ListNode temp = cur.next;
        cur.next = pre;
        pre = cur;
        cur = temp;
    }
    //此时的pre就是后半部分的头结点 然后判断是否值相同
    while (pre != null) {
        if (pre.val != head.val) {
            return false;
        }
        pre = pre.next;
        head = head.next;
    }
    return true;
}
复制代码


2)题友的实现方式


官方的题解:


1.复制链表值到数组列表中


2.使用双指针法判断是否为回文

微信截图_20220531200812.png


3.运行结果

微信截图_20220531200839.png

微信截图_20220531200907.png


三.题后思考


双指针法确实在很多算法题里都遇到了,其用法很普遍,掌握起来也不难,还有就是回文系列的题目都有共通点,做多了就明白里面的'套路'了。

目录
相关文章
|
1月前
【刷题记录】链表的回文结构
【刷题记录】链表的回文结构
|
1月前
|
算法
【算法】合并两个有序链表(easy)——递归算法
【算法】合并两个有序链表(easy)——递归算法
【算法】合并两个有序链表(easy)——递归算法
|
27天前
|
存储 算法
【初阶数据结构篇】顺序表和链表算法题
此题可以先找到中间节点,然后把后半部分逆置,最近前后两部分一一比对,如果节点的值全部相同,则即为回文。
|
30天前
|
算法
【数据结构与算法】共享双向链表
【数据结构与算法】共享双向链表
10 0
|
30天前
|
算法
【数据结构与算法】双向链表
【数据结构与算法】双向链表
10 0
|
30天前
|
算法
【数据结构与算法】循环链表
【数据结构与算法】循环链表
11 0
|
30天前
|
存储 算法
【数据结构与算法】链表
【数据结构与算法】链表
15 0
|
1月前
|
算法
【C算法】链表算法
【C算法】链表算法
|
1月前
|
算法 Java
LeetCode初级算法题:环形链表+排列硬币+合并两个有序数组java解法
LeetCode初级算法题:环形链表+排列硬币+合并两个有序数组java解法
43 0
|
1月前
|
存储 算法 Java
LeetCode初级算法题:反转链表+统计N以内的素数+删除排序数组中的重复项Java详解
LeetCode初级算法题:反转链表+统计N以内的素数+删除排序数组中的重复项Java详解
17 0