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

Question

这是在 IBM ISL 采访中被问到的。

我回答了这个问题，How to find the middle node of a single linked list in a single traversal (if the length of the list is not given)但它不包含我正在寻找的答案，所以再次张贴在这里。

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

我回答了，取 2 个指针 p1 和 p2 将 p2 移动 2 个节点，将 p1 移动 1 个节点。当p2为null时，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];
}