234 回文链表

01

题目信息

题目地址: https://leetcode-cn.com/problems/palindrome-linked-list/

请判断一个链表是否为回文链表。

示例 1:

输入: 1->2
输出: false

示例 2:

输入: 1->2->2->1
输出: true

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

02

解法一:数组

比较容易想到的就是使用另一个容器存节点,再比较值,这里存到数组进行首尾比较

public boolean isPalindrome(ListNode head) {
    List<Integer> vals = new ArrayList();
    // 将链表的值复制到数组中
    ListNode cur = head;
    while (cur != null) {
        vals.add(cur.val);
        cur = cur.next;
    }
    // 使用双指针判断是否回文
    int length = vals.size();
    for(int i = 0, j = length -1; i < length/2; i++,j--){
        int val1 = vals.get(i);
        int val2 = vals.get(j);
        if( val1 != val2 ) return false;
    }
    return true;
}

03

解法二:快慢指针

我们仍然是要使空间复杂度为O(1) 的,所以还是要回到纯链表的操作。结合之前的练习可以采用原地链表反转的算法之后再和原链表挨个比较,整个反转再比较的话是行不通的因为我们要用原地的不存储另外的链表,并且本来只用比较一半,所以我们这里要去找到链表的中间,并把后一半反转再进行前一半比后一半即可。

通过快慢指针,fast为slow两倍速度,最后fast为空时slow就停在后一半的开头(长度为偶数)如果是奇数呢?

定位之后进行反转,再进行双指针比较直到后一半走完

代码如下:

public boolean isPalindrome(ListNode head) {
    ListNode fast = head; 
    ListNode slow = head;
    //通过快慢指针找到中点
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    //如果fast不为空,说明链表的长度是奇数个
    if (fast != null) {
        slow = slow.next;
    }
    //反转后半部分链表
    slow = reverseList(slow);
    fast = head;
    while (slow != null) {
        //然后比较,判断节点值是否相等
        if (fast.val != slow.val) return false;
        fast = fast.next;
        slow = slow.next;
    }
    return true;
}
//反转链表
public ListNode reverseList(ListNode head) {
    ListNode cur = head;
    ListNode next = null;
    while( cur != null){
        //记住原链表的下一个
        ListNode temp = cur.next;
        //设下next
        cur.next = next;
        //更新next与cur
        next = cur;
        cur = temp;
    }
    return next;
}

04

总结

先是解法一也是和前面写的几题一样无脑解决的方式就是用另外的容器操作解除只能往下取的限制无论是数组也好还是也好都是用另外的容器直接进行我们想要的指针操作,接下来就是去挖掘链表的操作,只能next不能像数组一样任意使用索引的情况下我们怎么定位我们想要的地方,快慢指针的一个应用无论是在这题还有前面的删除倒数第几位的节点,以及明天要完成的一题环形链表都有体现。

本文分享自微信公众号 - IT那个小笔记(Jasper-zh_blog),作者:木瓜煲鸡脚

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-12-16

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 234. 回文链表

    Michel_Rolle
  • LeetCode 234. 回文链表

    freesan44
  • Leetcode 234. 回文链表

    若要满足 O(1) 空间复杂度,则不能借助于列表或栈结构存储数据。因为单链表不像字符串可以进行直接访问,所以这里采用的方式为,找到单链表中间元素,并反转单链表前...

    zhipingChen
  • LeetCode 234:回文链表 Palindrome Linked List

    Given a singly linked list, determine if it is a palindrome.

    爱写bug
  • LeetCode 234:回文链表 Palindrome Linked List

    Given a singly linked list, determine if it is a palindrome.

    爱写bug
  • LeetCode 234. 回文链表(快慢指针+链表反转)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/palindrome-linked-list 著作权...

    Michael阿明
  • Leetcode|234. 回文链表(链表的前后序遍历)

    SL_World
  • 链表问题-LeetCode 206、234、160(反转,回文,公共结点)

    示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

    算法工程师之路
  • 回文链表

    一份执着✘
  • 回文链表

    大忽悠爱学习
  • 回文链表

    _kyle
  • leetcode链表之回文链表

    这里使用Stack来解决,先遍历一遍放到Stack中,之后再次遍历,挨个跟stack.pop出来的比较

    codecraft
  • leetcode链表之回文链表

    这里使用Stack来解决,先遍历一遍放到Stack中,之后再次遍历,挨个跟stack.pop出来的比较

    codecraft
  • LeetCode26|回文链表

    这道题的解法虽然解法比较简单,但是耗时多,这里就不多说了,不过也通过了题目的测试用例,不知道后面有没有时间来做一下这个题的优化,目前这样的题都是采用很常规的思路...

    码农王同学
  • LeetCode65|回文链表

    码农王同学
  • Swift 回文链表 - LeetCode

    韦弦zhy
  • 链表回文判断(C++)

    xiaoxi666
  • 单链表回文判断

    判断一个单链表是否为回文链表目前有两种实现思路。一种是通过数组记录前半部分与后半部分依次比较,一种是找到链表中间结点,将左半部分反转与右半部分依次比较,下面详细...

    WindCoder
  • 漫谈递归-回文链表

    执行用时: 20 ms, 在Palindrome Linked List的C++提交中击败了42.09% 的用户

    程序员小王

扫码关注云+社区

领取腾讯云代金券