java实现了一个函数来检查链表是否是回文无递归、无堆栈、无反转

Question

我只是为这一个写了一个代码，我没有使用任何常见的解决方案，比如stack/reverse/recusion，我只是想知道这个解决方案是否好。 算法： 从开始和结束检查节点数据，每次我检查两个节点，一个从开始，另一个从结束。每一次一步一个头，跑步者都会被更新为一条新的尾巴

算法对我来说很好，我检查了很多输入，只是想知道为什么不是解决方案选项之一。谢谢：）

public static boolean isAPalindrom(Node head, Node tail)
{
    int count = 0;
    Node node = head;
    Node curr = head;
    Node runner = head;

    //count = linked list size
    while (node!= null)
    {
        count++;
        node = node.next;
    }

   if(head.data != tail.data)
       return false;


   //we need size/2-1 times to check a palindrom since we check 2 nodes each time head and tail
   for(int i=0 ; i<count/2 - 1; i++)
   {
       //head is each time step by one
       curr = curr.next;
       //runner back to head each time
       runner = head;

       while(runner.next != tail)
           runner = runner.next;


       if(curr.data != runner.data)
           return false;

       //new tail to check the next time
       tail = runner;
   }

   return true;
}

Answer 1

通常，我们根据good算法的时间复杂度和空间复杂度来确定它

您的解决方案在时间复杂度方面并非如此。我们可以很容易地得到一个O(n)解决方案，而你的解决方案是O(n^2)

对于空间，与使用堆栈等其他解决方案相比，您的解决方案是好的。您的解决方案解决了问题in place，这意味着它需要O(1)空间，而其他解决方案通常需要O(n)空间

但是请注意，一般来说，我们更关心time complexity，而不是space complexity

Answer 2

这种方法的问题在于（除非你的节点是“双链接的”），你的速度会很慢。 每次比较都需要你“跑”到新的终点：n+（n-1）->；n^2/2~

其他方法花费的时间（n~）要少得多，但占用了一些空间

编辑：对你的解决方案的一个小的（但很容易的）改进是开始以curr而不是head运行，但时间复杂性（遗憾的是）不会随着这次升级而改变