最近去面试，他们问我“在不使用任何额外存储的情况下，检查下面的双向链表是否是回文，例如STL的链表、堆栈、队列、树、字符串、字符数组等。”虽然我无法给出完美的解决方案。
下面是双向链表的图像：
这不是一个家庭作业问题，而只是一个寻找任何解决方案的问题。
问问题
3434 次
5 回答
4
这里的问题是您有自然迭代器，其元素可以是多个字符，但您只想对字符序列进行操作。所以我会定义另一个迭代器类型，它的行为方式符合我们的需要，使用boost::iterator_facade. （通常这种事情boost::iterator_adaptor更方便，但在这种情况下它无济于事。）
该图建议使用类似 C 的原始结构和指针设置，因此我假设自定义双向链表定义如下：
struct list_node {
list_node* prev;
list_node* next;
const char* data;
};
class LinkedList {
public:
list_node* head() const;
list_node* tail() const;
// ...
};
自定义迭代器类需要包含一个list_node*指针和一个指向char数组元素的指针。
#include <boost/iterator_facade.hpp>
class ListCharIter :
public boost::iterator_facade<
ListCharIter, // Derived class for CRTP
const char, // Element type
std::bidirectional_iterator_tag > // Iterator category
{
public:
ListCharIter() : m_node(nullptr), m_ch(nullptr) {}
// "Named constructors":
static ListCharIter begin(const LinkedList& listobj);
static ListCharIter end(const LinkedList& listobj);
private:
list_node* m_node;
const char* m_ch;
ListCharIter(list_node* node, const char* where)
: m_node(node), m_ch(where) {}
// Methods iterator_facade will use:
char dereference() const;
bool equal(const ListCharIter& other) const;
void increment();
void decrement();
// And allow boost to use them:
friend class boost::iterator_core_access;
};
仅对于一个过去的迭代器，我们将允许m_ch指向最后一个节点的 terminating '\0'。在没有元素的列表的特殊情况下，我们将为单个迭代器设置两个成员 null ，该迭代器既是开始又是结束并且不能被取消引用。
inline ListCharIter ListCharIter::begin(const LinkedList& listobj)
{
list_node* node = listobj.head();
const char* str = nullptr;
if (node) {
str = node->data;
}
return ListCharIter(node, str);
}
inline ListCharIter ListCharIter::end(const LinkedList& listobj)
{
list_node* node = listobj.tail();
const char* nul = nullptr;
if (node) {
nul = node->data;
while (*nul != '\0') ++nul; // Find the '\0'.
}
return ListCharIter(node, nul);
}
dereference()并且equal()是微不足道的：
inline char ListCharIter::dereference() const
{ return *m_ch; }
inline bool ListCharIter::equal(const ListCharIter& other) const
{ return this->m_node == other.m_node && this->m_ch == other.m_ch; }
最后，要前进或后退，基本思想是只有m_ch在有意义的情况下才改变，m_node否则就改变。
inline void ListCharIter::increment()
{
++m_ch;
// If m_node->next is null, we're advancing
// past the end of the entire list.
while (*m_ch == '\0' && m_node->next) {
m_node = m_node->next;
m_ch = m_node->data; // Start of new node.
// while loop repeats if m_node contains "".
}
}
inline void ListCharIter::decrement()
{
if (m_ch == m_node->data) {
// Already at the start of this node.
do {
m_node = m_node->prev;
m_ch = m_node->data; // Start of new node.
// while loop repeats if m_node contains "".
} while (*m_ch == '\0');
// Find the char before the terminating nul.
while (m_ch[1] != '\0') ++m_ch;
} else {
--m_ch;
}
}
现在您可以在普通回文算法（和许多其他算法）中使用该自定义迭代器。
template<typename BidirIter>
bool is_palindrome(BidirIter start, BidirIter stop)
{
for (;;) {
if (start == stop) return true;
if (*start != *stop) return false;
++start;
if (start == stop) return true;
--stop;
}
}
bool is_palindrome(const LinkedList& the_list)
{
return is_palindrome(ListCharIter::begin(the_list),
ListCharIter::end(the_list));
}
于 2013-09-24T16:40:07.220 回答
3
template<typename List>
bool isPalindrome(List const &list) {
auto b = list.begin();
auto e = list.end();
while (b != e) {
--e;
if (b == e) // for lists with exactly 1 or an even number of elements
break;
if (*b != *e)
return false;
++b;
}
return true;
}
We can't use > or >= because list iterators are not random access (in most imlementations) and so can only be compared equal/not-equal. std::distance is an option, but for non-randomaccess iterators it just does a whole lot of incrementing, which is slow. Instead, the check in the middle of the loop handles the greater-than case, so that the entire function can be written using only equality comparisons.
于 2013-09-24T15:08:17.923 回答
3
声明两个迭代器，start 和 end。然后遍历列表并同时减少/增加它们，在每一步进行比较。注意：此算法假定您已正确覆盖运算符，但它也适用于任何类型的列表，而不仅仅是数字列表。
for(int i=0;i<list.size()/2;i++){
if(*start!=*end) return false;
start++;
end--;
}
return true;
这里的关键是您使用的是迭代器，而不是直接使用列表。
于 2013-09-24T14:53:40.560 回答
2
这是我用于回文测试的代码。它需要两个迭代器并正确处理空范围和奇/偶长度范围。
template <typename BidIt>
bool is_palindrome(BidIt first, BidIt last)
{
if (first == last) return false; // empty range
for (;;) {
if (first == --last) break;
if (*first != *last) return false; // mismatch
if (++first == last) break;
}
return true; // success
}
于 2013-09-24T15:33:43.173 回答
0
我想添加一个C++11解决方案（由于基于范围的for循环和auto说明符），它使用std::list,std::advance()和std::equal()，从而产生非常短的代码：
#include <list>
#include <algorithm>
#include <iostream>
using namespace std;
int main()
{
// Fill a doubly-linked list with characters.
string str = "racecar";
list<char> l;
for (char c : str)
l.emplace_back(c);
// Find the center of the list.
auto it = l.begin();
advance(it, l.size() / 2);
// Compare the first half of the list to the second half.
if (equal(l.begin(), it, l.rbegin()))
cout << str.c_str() << " is a palindrome." << endl;
else
cout << str.c_str() << " is not a palindrome." << endl;
return 0;
}
输出：
赛车是回文。
注意 1：此解决方案的效率可能低于其他答案，因为它必须先遍历列表的一半才能找到其中心。但是，恕我直言，它看起来不那么复杂。
注 2：该函数equal()将列表的前半部分与后半部分以相反的顺序进行比较，list::rbegin()因为 增加此迭代器会将其移向列表的开头。
注意3：如果您想将代码应用于不同类型的容器，您可以将其放入函数模板中，如大多数其他答案所示。
于 2018-07-13T14:18:01.843 回答