单链表是否是回文

Question

我有一个单链接列表.我想知道链接列表是否是Palindrome.我已经以下面的一种方式实现了它.

bool palindromeOrNot(node *head) {
  node *tailPointer;
  node *headLocal=head;
  node *reverseList=reverseLinkedListIteratively(head);
  int response=1;

  while(headLocal != NULL && reverseList!=NULL) {
    if(headLocal->id==reverseList->id) {
      headLocal=headLocal->next;
      reverseList=reverseList->next;
    }
    else
      return false;
  }

  if(headLocal == NULL && reverseList==NULL)
    return fasle;
  else 
    return true;
}

我正在反转原始链接列表,然后比较Node by Node.如果一切都很好,那么我将返回1,否则返回0.

有没有更好的算法来解决这个问题.

Answer 1

方法1(使用堆栈)

一个简单的解决方案是使用一堆列表节点.这主要涉及三个步骤.

1. 从头到尾遍历给定列表并将每个访问的节点推送到堆栈.
2. 再次遍历列表.对于每个被访问节点,从堆栈弹出一个节点,并将弹出节点的数据与当前访问的节点进行比较.
3. 如果所有节点都匹配,则返回true,否则返回false.

上述方法的时间复杂度为O(n),但需要O(n)额外空间.以下方法通过恒定的额外空间解决此问题

方法2(通过颠倒列表)

该方法需要O(n)时间和O(1)额外空间.

1. 获取链接列表的中间位置.
2. 反转链表的后半部分.
3. 检查前半部分和后半部分是否相同.
4. 通过再次反转后半部分并将其附加回上半部分来构建原始链接列表

方法3(使用递归)

左右两个指针.使用递归向右和向左移动,并在每次递归调用中检查以下内容.

1. 子列表是回文.
2. 当前左右的值是匹配的.

如果以上两个条件均为真,则返回true.

我们的想法是使用函数调用堆栈作为容器.递归遍历直到列表的末尾.当我们从最后一个NULL返回时,我们将在最后一个节点.要与列表的第一个节点进行比较的最后一个节点.

为了访问列表的第一个节点,我们需要在最后一次递归调用中使用列表头.因此我们也将头传递给递归函数.如果它们都匹配,我们需要比较(2,n-2)个节点.再次当递归回落到(n-2)nd节点时,我们需要从头部引用第二个节点.我们在前一次调用中前进头指针,以引用列表中的下一个节点.

但是,识别双指针的技巧.传递单个指针和传值一样好,我们将一次又一次地传递相同的指针.我们需要传递头指针的地址,以反映父递归调用的变化.

更多:geeksforgeeks

Answer 2

Whether a single-linked list is Palindrome or not,也可以检查 without reversing the linked list

可以接近递归方法,其中将指向指向链表开始的指针,并且将比较从最后一个递归返回的另一指针.

这是伪代码:

int isPalindrome(**root,*head)
{
if(!head)
    return 1;
else
{
    int res = isPalindrome(root,head->next);

    if(res == 0)
        return 0;
    int r = (*root)->data == head->data;
    *root = (*root)->next;
    return r;
}
} 

呼叫如下: isPalindrome(&root,root);

Answer 3

你为什么要把事情搞复杂。由于这是一项家庭作业，我只能给你一个简单的建议。我发现您只是比较代码中的 id。假设你的 id 是一个字符，为什么不简单地遍历一次列表并将字符存储在一个数组中，然后检查回文。你的方法只是简单地反转链表一次并遍历链表两次，总共有三次遍历函数。