leetcode234-回文链表 java

逃离我推掉我的手 2023-06-13 06:20 2阅读 0赞

### 文章目录 ###

*  回文链表
 *   *  题目描述
     *  code
     *   *  方法一
         *   *  解题思路
             *  提交结果
         *  方法二

# 回文链表 #

## 题目描述 ##

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

示例 1:

输入: 1->2
    输出: false

示例 2:

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

## code ##

### 方法一 ###

#### 解题思路 ####

> 使用双指针做法，一个快指针，一个慢指针，当快指针走到链表结尾的时候，慢指针走向中间位置，然后使用栈stack 进行存储，然后进行比较 栈中的元素和前一半的元素是否是回文数字，是否相同

class Solution {
            private Stack<ListNode> stack = new Stack<>();
            public boolean isPalindrome(ListNode head) {
                if (head == null) {
                    return true;
                }
                ListNode slow = head;
    
                ListNode fast = head;
    
                while (fast != null && fast.next != null) {
                    slow = slow.next;
                    fast = fast.next.next;
                }
                //找到中点, 将数据放入栈中
                while (slow != null) {
                    stack.push(slow);
                    slow = slow.next;
                }
                //进行比较
                ListNode left = head;
                while (!stack.isEmpty()) {
                    //进行比较
                    ListNode right = stack.pop();
                    if (left.val == right.val) {
                        //继续进行比较
                        left = left.next;
                    }else{
                        return false;
                    }
                }
    
                return true;
            }
        }

#### 提交结果 ####

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Yw19sZf8-1573723128365)(21235E87F2144FA59EADFA0B87DAE371)\]][img-Yw19sZf8-1573723128365_21235E87F2144FA59EADFA0B87DAE371]

> 还是需要进行优化, 其实题目中也有进阶要求，用O(n) 时间复杂度和O(1)的空间复杂度解决这个问题

### 方法二 ###

> 一边遍历，一边改变链表的指向，然后找到中位的时候，分别从两边进行遍历，判断是否相同

/**
         * 方式二： 进行优化
         * 在leetcode中看到一种思路， 一边遍历，然后就改变指针方向，这样找到中间位置后， 就可以从中间位置，
         * 分别向两边顺序遍历，  就可以判断是否是回文链表， 思路很厉害 ， 值得学习， 有了这个思路以后，
         * 自己进行写代码完成
         */
        class Solution {
            public boolean isPalindrome(ListNode head) {
                //如果链表为空，直接返回true，测试用例中是这样的，没有办法
                if (head == null) {
                    return true;
                }
                //快慢指针做法
                ListNode slow = head;
                ListNode fast = head;
                ListNode pre = head; //slow 慢指针的前置指针，记录位置
                ListNode prepre = null; //prepare是head节点的前一个节点，为null
                while(fast != null && fast.next != null) {
                    pre = slow;
                    slow = slow.next;
                    fast = fast.next.next;
                    pre.next = prepre;
                    prepre = pre;
                }
                if(fast != null) {
                    slow = slow.next;
                }
                while(pre != null && slow != null) {
                    if(pre.val != slow.val) {
                        return false;
                    }
                    pre = pre.next;
                    slow = slow.next;
                }
                return true;
            }
        }

[img-Yw19sZf8-1573723128365_21235E87F2144FA59EADFA0B87DAE371]: https://img-blog.csdnimg.cn/20191114172306377.png