c++ - 给定具有奇数个节点的单个链表，通过仅遍历列表一次找到中间节点的两种方法是什么？

Question

这是在 IBM ISL 采访中提出的。

我经历了这个问题，如何在单次遍历中找到单个链表的中间节点（如果未给出列表的长度），但它不包含我正在寻找的答案，所以再次在这里发布。

我有一个单链表，假设节点数是奇数。告诉我通过遍历列表一次找到中间节点的两种方法？

我回答说，用 2 个指针 p1 和 p2 将 p2 移动 2 个节点，将 p1 移动 1 个节点。当 p2 为空时，p1 在中间节点。

面试官回答：这是最简单的方法，使用 2 指针。再告诉我一种方法。提示：是否有可以使用的编译器属性？

有人可以给我一种使用提示的方法吗？

Answer 1

#include <vector>
#include <list>

typedef std::list<int> listT;

listT::const_iterator
find_middle(const listT &list)
{
  std::vector<listT::const_iterator> v;
  for (listT::const_iterator i = list.begin() ; i != list.end() ; ++i)
    v.push_back(i);

  return v[v.size() / 2];
}