preface:
In order to better self-monitoring and exercise your code ability, start to brush questions. There are 100 questions in total, 6 questions a day. There are still 20 days left in the holiday, and you can finish it.
Two questions in the morning, two questions in the afternoon and two questions in the evening.

Title Description:

Idea of rearrangement linked list algorithm:
(1) First, find the middle node of the linked list
(2) Reverse the order of the second half of the linked list
(3) Merge the first half of the list with the second half of the list in reverse order. The idea of merging is to take a node from each of the two lists for merging

main function:
int main(){
ListNode *head=createByTail();
Solution().reorderList(head);
displayLink(head);
return 0;
}

First, use the tail interpolation method to create the linked list. Here, the topic requires to use the single linked list without the leading node for operation, so it is like the previous ListNode * head = new ListNode; Codes such as head - > next = null are no longer used, but directly ListNode *head;head=NULL; Just because the single linked list of the leading node must have a new ListNode, but not for headless nodes.
So there are the following codes:

ListNode *creatByTail(){
	ListNode *head;
	ListNode *p;
	ListNode *tail;
	int n=0,num;
	int len;
	cin>>len;
	head=NULL;
	while(n<len && cin>>num){
		p=new ListNode;
		p->val=num;
		p->next=NULL;
		n=n+1;
		if(n==1){
			head=p;
		}
		else{
			tail->next=p;
			}
		tail=p;
}
	return head;
}

After creating the linked list, you need to operate the linked list. Let's review the idea of the algorithm:
(1) First, use the speed pointer to find the middle node of the linked list
(2) Then reverse the linked list after the intermediate node
(3) Take the first half of the linked list including intermediate nodes as list1, and the last part of the linked list after reverse order as list2. Cross merge list1 and list2.

First, use the fast and slow pointer to find the middle node of the linked list. The principle is that the fast pointer takes two steps at a time and the slow pointer takes one step at a time to traverse the linked list. When fast - > next = null or fast - > next - > next = = null, it means that the linked list has to be traversed. At this time, the slow pointer just goes to the middle of the linked list. The code is as follows:

ListNode *middleNode(ListNode *head){
	ListNode *fast=head;
	ListNode *slow=head;
	while(fast->next!=NULL && fast->next->next!=NULL){
		slow=slow->next;
		fast=fast->next->next;
		}
	return slow;
}

Using the above code, we can find the intermediate node of the linked list. After finding it, we said to reverse the chain list at the back of the intermediate node. I refer to this article for the idea of reverse order Reverse order thought
I think the author writes very well. I'll study it again here.
Reverse order thought:
(1) If it is an empty linked list, that is, head==NULL, it is returned directly.
(2) if head!=NULL; then use three pointers, ListNode *prev=NULL; (used to refer to the forward pointer)
ListNode *curr=head; (used to point to the current pointer)
ListNode *nextTemp=curr->next; (used to point to the back pointer)
(3) When traversing the linked list, the judgment factor of the loop is whether curr is NULL. NULL means that the loop jumps out when the end of the linked list is reached. Otherwise, the logic in the loop is executed in the linked list:
Point the next node of the current node pointed by curr to prev, that is, curr - > next = prev. At this time, prev=NULL, then the next node of curr is empty, indicating that it is the last node now. Then point the prev pointer to curr and curr to nexttemp, that is, prev=curr;curr=nextTemp; Then proceed to the next cycle.
The code is as follows:

ListNode *reverseLink(ListNode *head){
	ListNode *prev=NULL;
	ListNode *curr=head;
	while(curr!=NULL){
		ListNode nextTemp=curr->next;
		curr->next=prev;
		prev=curr;
		curr=nextTemp;
	}
	return prev;
}

After reversing the linked list after the intermediate node, we need to merge. Before merging, let's see how we change the original linked list into two linked lists:

			ListNode *mid=middleNode(head);
			ListNode *list1=head;
			ListNode *list2=mid->next;
			mid->next=NULL;
			list2=reverseList(list2);
		}

First find the intermediate node mid, then assign the head of the original linked list to list1, and assign mid - > next to list2, that is, assign the next node pointed by the intermediate node to list2. Then assign mid - > next to NULL, indicating that list1 is over to mid, and then reverse list2.

Let's look at the final merge operation. The merge operation is very simple. It uses two temporary variables, one to traverse the elements in list 1 and the other to traverse the elements in list 2. First, insert the first element of list 2 into the first element of list 1, and then insert the second element of list 1 behind the first element of list 2. The code is as follows:

void mergeList(LixtNode *list1,ListNode *list2){
	ListNode *list1_temp;
	ListNode *list2_temp;
	while(list1!=NULL && list2!=NULL){
		list1_temp=list1->next;
		list2_temp=list2->next;

		list1->next=list2;
		list1=list1_temp;

		list2->next=list1;
		list2=list2_temp;
		}
}
		

The complete code is as follows:

#include<iostream>
using namespace std;

//Idea of rearrangement linked list algorithm:
//(1) First, find the middle node of the linked list
//(2) Reverse the order of the second half of the linked list 
//(3) Merge the first half of the list with the second half of the list in reverse order
//The idea of merging is to take a node from each of the two linked lists for merging 
struct ListNode{
	int val;
	ListNode *next;
	
}; 

class Solution{
	public:
		void reorderList(ListNode *head){
			if(head == NULL){
				return;
			}
			ListNode *mid=middleNode(head);//Find the middle node of the linked list
			ListNode *list1=head;
			ListNode *list2=mid->next;
			mid->next=NULL;
			list2=reverseList(list2);
			mergeList(list1,list2);
		}
		
		ListNode *middleNode(ListNode *head){
			ListNode *slow =head;
			ListNode *fast =head;
			while(fast->next!=NULL && fast->next->next!=NULL){
				slow=slow->next;
				fast=fast->next->next;
			}
			return slow;
		} 
		ListNode *reverseList(ListNode *head){
			ListNode *prev=NULL;
			ListNode *curr=head;
			while(curr!=NULL){
				ListNode *nextTemp=curr->next;
				curr->next=prev;
				prev=curr;
				curr=nextTemp;
			}
			return prev;
		}
		void mergeList(ListNode *list1,ListNode *list2){
			ListNode *list1_temp;
			ListNode *list2_temp;
			while(list1!=NULL && list2!=NULL){
				list1_temp=list1->next;
				list2_temp=list2->next;
				
				list1->next=list2;
				list1=list1_temp;
				
				list2->next=list1;
				list2=list2_temp; 
			}
		}
		
};


ListNode *createByTail(){
	
	ListNode *head;
	ListNode *p,*tail;
	int n=0,num;
	int len;
	cin>>len;
	head=NULL;
	while(n<len && cin>>num){
		p=new ListNode;
		p->val=num;
		p->next=NULL;
		n=n+1;
		if(n==1){
			head=p;
		}
		else{
			tail->next=p;
		}
		tail=p;
	} 
	
	return head;
}


void displayLink(ListNode *head){
	ListNode *p;
	p=head;
	cout<<"head-->";
	while(p!=NULL){
		
		cout<<p->val<<"-->";
		p=p->next;
	}
	cout<<"tail\n";
}


int main(){
	
	ListNode *head=createByTail();
	Solution().reorderList(head);
	displayLink(head);
	return 0;
}