Example 1:

Input: [1,2,3,4,5]

Output: Node 3 from this list (Serialization: [3,4,5])

The returned node has value 3.(The judge's serialization of this node is[3,4,5]).

Note that we returned a ListNode object ans, such that:

ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, and ans.next.next.next = NULL.

Example 2:

Input: [1,2,3,4,5,6]

Output: Node 4 from this list (Serialization: [4,5,6])

Since the list has two middle nodes with values 3 and 4, we return the second one.

#include <iostream>
using namespace std;

class node{
	public:
		int value;
		node * next;
	
	public:	
		node(int value = 0,node * next = NULL){
			this->value = value;
			this->next = next;
		}
};
node* middleNode(node* head) {
		node* middleNode = head; //走一步
		node* fastNode = head;   //走两步
		while(fastNode->next!= NULL){
			middleNode = middleNode->next; // fastNode 比 middleNode 走得快,不需要判断middle->next != NULL
			if(fastNode->next->next != NULL) fastNode = fastNode->next->next;
			else break;

			
		}
		if(!fastNode->next){middleNode = middleNode->next;}
		return middleNode;
}


int main(int argc, char *argv[]) {
	int m = 0;
	while(cin >> m){
		/*建立链表*/
		if(m==0) continue;
		node * head_first = new node(m);
		node * tail_first = head_first;
		for(int i = 0 ; i < m ; i ++){
			node * p = new node();
			int temp;
			cin >> temp;
			p->value = temp;	
			tail_first->next = p;
			tail_first = p;
		}
		/*输出链表*/
		node * head_1 = head_first->next;
		while(head_1){
			cout << head_1->value << " ";
			head_1 = head_1->next;
		}
		cout << endl;
		int mid = m/2+1;
		node * p = head_first;
		for(int i = 0 ; i < mid ; i ++){
			p = p->next;
		}
		cout << p->value << endl;
		
		cout << middleNode(head_first)->value << endl;
		
	}
}