单链表是否回文 [英] 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.

推荐答案

方法一(使用堆栈)

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

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. 当前左侧和右侧的值匹配.

如果以上两个条件都为真，则返回真.

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屋！