링크 의 중간 점 을 찾다.

//        

/*

     L，                 。



  ：

1、             ，    。        ，            。      O(3n/2)

2、     ：      ，        ，        ，      NULL   ，               



          

*/





#include <iostream>

#include <string>



using namespace std;



int L_length = 0;







template<class T>

struct Node {

    T value;

    Node *next;

    Node() {

        next = NULL;

    }

    Node(const T &data) {

        value = data;

        next = NULL;

    }

};



template<class T>

void PushinList(Node<T>* &L, const T &t) {

    Node<T> *n = new Node<T>(t);

    n->next = L->next;

    L->next = n;

    L_length++;

}



template<class T>

void PrintList(const Node<T>* L) {

    cout << "    ：";

    for (Node<T>* p = L->next; p != NULL; p = p->next) cout << p->value << " ";

    cout << endl;

}



template<class T>

Node<string>* GetMiddle(const Node<T>* L) {

    Node<string> *p_fast, *p;

    p = p_fast = L->next;

    while (p_fast) {

        p_fast = p_fast->next;

        if (p_fast) p_fast = p_fast->next;

        else break;

        p = p->next;

    }

    return p;

}







int main(void) {

    Node<string>* L = new Node<string>();

    string str;

    cout << "    ( -1  )：";

    while (cin >> str && str != "-1")

        PushinList(L, str);

    PrintList(L);

    Node<string>* p = GetMiddle(L);



    cout << "     " << p->value << endl;



    system("pause");

    return 0;

}



/*

    ：

a b c d e f g -1

a b c d e f -1

    ：

d

c

*/