c - 检查单个链接列表中的回文

Question

可能重复：
单链表是否为回文

假设我有一个包含 char 项的链接列表，我需要查找该链接列表中的字符是否为回文。我知道链接列表根本不是一个合适的结构，但是如果我们有一个怎么办？

例如a-b-c-b-a

双向链表很简单，我们可以从头尾开始

ptrh=head ptrt=tail
if(ptrh->item==ptrt->item)

和

ptrh->ptrh->frwdlink
ptrt->ptrt->bcklink

但是如果我们有一个单链表呢？那怎么实现呢？

Answer 1

知道列表的大小，您就可以知道中间是什么。然后，当您浏览时，您只需将所有字符缓存到中间，并确保它们在中间之后以相反的顺序出现。

Answer 2

你可以创建临时数组吗？将链表中的所有项放入一个数组中，然后将索引 n 与索引 (length - n) 进行比较。

var ptr = head; var array = [];

while (ptr != null)
{
  array.push(ptr.item);
  ptr = ptr.next;
}

for (var i = 0; i < array.length / 2; i++)
{
  if (array[i] != array[array.length - i])
    return (false);
}

return (true);

Answer 3

您可以在第一次浏览列表时构建一个节点顺序相反的列表。

然后比较原始列表和倒排列表的前 n/2+1 个节点