【力扣】234.回文链表

2023-12-13 04:36:23

嗯,今天这道题是我自己写的哦~,哒哒哒。今天还是很不错滴~

234.回文链表

说一下我的解题思路,首先我的想法很简单就是将这个链表反转,然后将反转之后的链表与原链表进行对比。相等就返回true,不相等就返回false。所以我就想到了昨天写了那个反转链表的题目,那就在想是不是可以简单的借鉴一下呢,反正道理是通的。这么一写就出问题了。我对于链表的掌握情况就像是手握沙子一下,其实没多少。呜呜呜~

好,回来。

针对反转链表的那个题目(代码如上),head指针指向的是反转之后的尾部,因为它之前是头部,对吧,所以head.next的值应该是null,所以看下面的代码(我自己写的关于本题的代码)虽然当head=[1,2,2,1]时确实是满足了题目条件,但是当head=[1,2,1,1]的时候就暴露了,因为他在应该返回false的时候,选择了返回true!简直不能忍受,而且是只比较了一轮就结束了。这样的解法不太保险,但是我还是想坚持一下。

原因:

后面发现了自己的问题,于是进行了改进,代码如下:

问题就是我改变了原有的链表的结构,指针的指向完全变了。

而在改进的代码中我创建了一个结点用于保存现有的指针的值

reversed用于存储反转后的链表,所以完成!

代码:

/**
 * 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) {
       if (head == null || head.next == null) {
            return true;
        }

        // 迭代反转链表
        ListNode reversed = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode newNode = new ListNode(curr.val);
            newNode.next = reversed;
            reversed = newNode;
            curr = curr.next;
        }

        // 比较原始链表和反转后的链表的值
        while (head != null && reversed != null) {
            if (head.val != reversed.val) {
                return false;
            }
            System.out.print(head.val);
            head = head.next;
            reversed = reversed.next;
        }

        // 如果能够遍历完两个链表,说明是回文链表
        return true;
    }
}

真不容易,脑筋转过来的过程是痛苦的,真的。但是很爽!

其实还有很多种解法,但是我就暂时只写这个啦~

祝你生活愉快,刷题快乐!

文章来源:https://blog.csdn.net/qq_62649563/article/details/134882203
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。