个人中心
gpt4 book ai didi

LeetCode_双指针_简单_234.回文链表

转载 作者：知者 更新时间：2024-03-13 08:23:49 26 4
gpt4 key购买 nike

1.题目

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

示例 1：

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

示例 2：

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

提示：
链表中节点数目在范围[1, 105] 内
0 <= Node.val <= 9

进阶： 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindrome-linked-list

2.思路

（1）双指针——将值复制到数组中
由于单链表无法倒着遍历，故可以先将链表中的值复制到数组中，然后再使用双指针法判断是否为回文即可。该方法的时间复杂度和空间复杂度均为O(n)。
（2）双指针——快慢指针
① 通过快慢指针 fast 和 slow 找到链表的中点；
② 从 slow 指针开始反转后面的链表；
③ 最后使用双指针判断回文即可。

3.代码实现（Java）

//思路1————双指针——将值复制到数组中
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        List<Integer> values = new ArrayList<Integer>();
        //将链表中的值复制到数组values中
        ListNode curNode = head;
        while (curNode != null) {
            values.add(curNode.val);
            curNode = curNode.next;
        }     
        //使用双指针判断回文
        int left = 0, right = values.size() - 1;
        while (left < right) {
        	//在比较Integer类型的值时，使用equals()比较更合适
            if (!values.get(left).equals(values.get(right))) {
                return false;
            } else {
            	//移动指针
                left++;
                right--;
            }
        }
        return true;
    }
}
//思路2————双指针——快慢指针
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode slow = head, fast = head;
        //通过快慢指针找到链表的中点
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        //如果fast指针没有指向null，说明链表⻓度为奇数，slow还要再前进⼀步
        if (fast != null) {
            slow = slow.next;
        }
        //从slow指针开始反转后面的链表
        ListNode left = head, right = reverse(slow);
        //使用双指针判断回文
        while (right != null) {
            if (left.val != right.val) {
                return false;
            } else {
                //移动指针
                left = left.next;
                right = right.next;
            }
        }
        return true;
    }
    
    //反转以head为头结点的链表
    public ListNode reverse(ListNode head) {
        ListNode pre = null, cur = head, nxt = head;
        while (cur != null) {
            nxt = cur.next;
            // 逐个结点反转
            cur.next = pre;
            // 更新指针位置
            pre = cur;
            cur = nxt;
        }
        // 返回反转后的头结点
        return pre;
    }
}

26 4 0
文章推荐： Java数据类型和MySql数据类型对应表
文章推荐： 利用python转换图片格式
文章推荐： Springboot笔记(4)：SpringBoot 自动配置原理/狂神说
文章推荐： java排序
知者
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com