java 检查链表是否是回文

rdlzhqv9  于 2023-09-29  发布在  Java
关注(0)|答案(3)|浏览(116)
public boolean palindromLinkedList() {
    //find size
    Node temp = head;
    int size=0;
    while(temp != null){
        size++;
        temp=temp.next;
    }
    //find while loop iteration
    int c;
    if(size%2 ==0){
        c = size/2;
    }else{
        c = (size+1)/2;
    }
    //intialise start and end pointer
    Node start = head;
    Node end = tail;
    //index pointer
    int k =size-1;
    //loop for the palindrome condition
    while(c > 0)`
        if(start.data != end.data){
            return false;
        }
        start = start.next;
        Node find = head;
        k--;
        for(int i=0;i<=k;i++){
            find = find.next;
        }
        end = find;
        c--;
    }
    return true;
}

我尝试使用类似于两个指针的方法来检查链表是否是回文。
我初始化了两个变量:start = headend = tail
Start从start开始检查节点,end从tail开始检查,在检查start和end值的数据是否相等后,我将更改后的起始点设置为下一个节点,并使用for循环查找end的前一个节点,并继续此过程,直到指针到达中间节点。
如果链表是回文,则返回true或false。我认为我的方法是正确的,但似乎有什么我错过了。

du7egjpx

du7egjpx1#

看起来你实现了自己的链表,这使得这个问题很难回答。
但是,假设您的代码类似于java.util.LinkedList:
java中的==检查引用,而不是给定的Object。您应该使用.equals来比较节点数据。更好的是Objects.equals(start.data, end.data),因为它也可以处理null
这种行为的一个很好的例子是字符串。Java收集你在程序中硬编码的字符串,所以它有时能工作,但大多数时候不能。

"abc" == "abc" // true
"abc".equals("abc") // true
"abc" == new String("abc") // false
"abc".equals(new String("abc")) // true
"abc" == getUserPassword() // false
"abc".equals(getUserPassword()) // true if user enters abc

我建议你实现一个双向链表,因为它会提高性能,在这种情况下,让你的生活更容易。它基本上也添加了对前一个节点的引用。因此,您不需要循环遍历所有元素,而是可以使用end.previous获取前一个节点。

krcsximq

krcsximq2#

问题出在这行代码中:

for (int i = 0; i <= k; i++) {

此循环将一次迭代转化为多次迭代。更改为:

for (int i = 0; i < k; i++) {

这将解决即使是最简单的测试用例也会得到错误的输出。
但现在你会遇到另一个问题:这个代码太慢了。为了确定 * 在 * end之前的节点而必须执行的重复循环代价太高,并且使您的实现具有O(𝑛²)的时间复杂度。你得想个更好的主意。
这个问题以前已经解决过很多次了,而且在这个网站上,你会找到更有效的方法来解决这个问题的解释。

yacmzcpb

yacmzcpb3#

旁注:
你应该将“size”变量作为链表实现的一部分来存储,而不是用循环来计算它。你知道什么时候有东西被添加到你的链表中;大小加1。你知道什么时候有东西从你的链表中删除了;尺寸减1。
主要React:
如果不使用外部结构(如Stack),或者将链表转换为双向链表,您将不得不反复使用循环来找出“结束”位置的节点。
但是,您可以通过从“开始”位置开始并向前跳转所需的次数来减少迭代次数。
在第一次比较时,“结束”位置将是size - 1跳离“开始”。之后,每次跳跃的次数减少2次,因为“开始”向前移动了1次,“结束”向后移动了1次。
考虑到这一点,您可以简单地保持比较,只要(required number of jumps to get from "start" to "end" >= 1
它看起来像这样:

public boolean palindromLinkedList() {
    // find size
    Node temp = head;
    int size = 0;
    while(temp != null){
        size++;
        temp = temp.next;
    }

    // check corresponding pairs
    Node end;
    Node start = head;
    int jumps = size - 1;
    
    while (jumps >= 1) {
      end = start;
      for(int i=1; i<=jumps; i++) {
        end = end.next;  
      }

      // ... do your comparison using one of the below ...
      
      // assuming a REFERENCE type of "data" that has an equals() method
      if (!start.data.equals(end.data)) {
        return false;
      }

      // assuming a PRIMITIVE type of "data" (like int, double, etc)
      if (start.data != end.data) {
        return false;
      }
      
      jumps = jumps - 2;
      start = start.next;
    }
    
    return true; // no counter-example found
  }

相关问题