給定一個具有奇數個節點的單鏈表，有兩種方法只通過遍歷列表找到一箇中間節點？

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爲空時，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]; 
}