我有一个采访，他们问我，我不知道答案我得到一个答案

Question

问题是编写一个伪代码，返回true如果给定的单向链表读取相同的两个方向，否则为false。另外我们知道存储在变量n中的列表的大小。预期的解决方案应该具有计算复杂度O（n）和存储器复杂度O（1）。

例如：1-> 2-> 3-> 3-> 2-> 1返回真

例如：1-> 2-> 3-> 1-> 2-> 3返回假

Answer 1

可以颠倒一个单向链表，完成单个传递（参见本答案的结尾）。这项任务对额外内存的限制是相当有限的，所以我认为最好的方法有点难以理解。

1. 遍历列表和反向使用我上面提到的算法其中心之后到来时（n/2位置之后即）的部分。保存一个指向列表中最后一个元素的指针 - 您需要在步骤2中使用它。
2. 同时遍历列表从开头到位置n/2和反向部分（从n到n/2）。您在两部分中迭代的元素应该匹配。为此，您需要两个变量 - 一个迭代第一部分，一个迭代第二部分（还有一个记住已经处理了多少元素）。
3. 倒退列表的后半部分，以便列表在最后不被更改。

总的来说我满足了任务的要求。

扭转单向链表该算法是这样的（使用C++如例）：

struct node { 
    node* next; 
    int data; 
}; 

// reverses a one-way list and returns pointer to the new list head 
node* reverse(node* c) { 
    node* prev = NULL; 
    node* cur = c; 
    // I assume the list is NULL terminated; 
    while (cur) { 
    node* temp = cur->next; 
    cur->next = prev; 
    prev = cur; 
    cur = temp; 
    } 
    return prev; 
}