单链表是否为回文 [英] Single Linked List is Palindrome or not

问题描述

我有一个单链表.我想找到链接列表是否是回文. 我已经通过以下一种方式实现了它.

I have a Single Linked List. I want to find that Linked List is Palindrome or not. I have implemented it in One way as below.

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;
}

我要反转原始链表，然后逐个节点比较节点.如果一切都好 然后我将返回1，否则将返回0.

I am reversing the original Linked List and then comparing Node by Node. If everything is fine then I will return 1 else return 0.

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

Is there a better algorithm to solve the problem.

推荐答案

方法1(使用堆栈)

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

A simple solution is to use a stack of list nodes. This mainly involves three steps.

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

上述方法的时间复杂度为O(n)，但需要O(n)额外空间.下列方法可解决此问题，并提供恒定的额外空间.

Time complexity of above method is O(n), but it requires O(n) extra space. Following methods solve this with constant extra space.

方法2(通过反转列表)

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

This method takes O(n) time and O(1) extra space.

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

方法3(使用递归)

使用左右两个指针.使用递归在左右方向移动，并在每个递归调用中检查是否遵循以下条件.

Use two pointers left and right. Move right and left using recursion and check for following in each recursive call.

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

如果以上两个条件均成立，则返回true.

If both above conditions are true then return true.

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

The idea is to use function call stack as container. Recursively traverse till the end of list. When we return from last NULL, we will be at last node. The last node to be compared with first node of list.

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

In order to access first node of list, we need list head to be available in the last call of recursion. Hence we pass head also to the recursive function. If they both match we need to compare (2, n-2) nodes. Again when recursion falls back to (n-2)nd node, we need reference to 2nd node from head. We advance the head pointer in previous call, to refer to next node in the list.

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

However, the trick in identifying double pointer. Passing single pointer is as good as pass-by-value, and we will pass the same pointer again and again. We need to pass the address of head pointer for reflecting the changes in parent recursive calls.

更多: geeksforgeeks

这篇关于单链表是否为回文的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！