CodeTop - Sort odd ascending even descending linked list

subject

Code

#include <iostream>
#include <vector>
using namespace std; 

/*  Given an odd digit ascending order , Even bit descending list , Reorder them （ Ascending ）  example ：1->8->3->6->5->4->7->2->NULL 1->2->3->4->5->6->7->8->NULL  solution ： 1） First, install the parity sequence to split the linked list （1->3->5->7->NULL and 8->6->4->2->NULL) 2） Reverse even linked list (1->3->5->7->NULL and 2->4->6->8->NULL) 3） Merge two linked lists  */

typedef struct ListNode{
    
	int val;
	struct ListNode *next;
}ListNode, *LinkList;

void create(LinkList &head){
    
	int n;
	cin>>n;
	head = new ListNode;
	head->next = NULL;
	ListNode *tail = head;
	for(int i = 0; i < n; i++){
    
		ListNode *p = new ListNode;
		cin>>p->val;
		p->next = NULL;
		tail->next = p;
		tail = p;
	}
}

//  Split the parity linked list  
pair<ListNode*, ListNode*> partition(ListNode *head){
    
	//  Odd list initialization  
	ListNode *oddhead = new ListNode;
	oddhead->next = NULL;
	ListNode *oddtail = oddhead;
	//  Even linked list initialization  
	ListNode *evenhead = new ListNode;
	evenhead->next = NULL;
	ListNode *eventail = evenhead;
	int i = 1;  //  Record linked list order 
	while(head){
    
		ListNode *p = new ListNode;
		p->val = head->val;
		p->next = NULL;
		if(i % 2 == 1){
    
			oddtail->next = p;
			oddtail = p;
		}else{
    
			eventail->next = p;
			eventail = p;
		}
		head = head->next;
		i++;
	} 
	oddhead = oddhead->next;
	evenhead = evenhead->next;
	return {
    oddhead, evenhead};
}

//  Reverse a linked list 
ListNode* reverseLink(ListNode *head){
    
	ListNode *pre = NULL;
	ListNode *cur = head;
	while(cur){
    
		ListNode *temp = cur->next;
		cur->next = pre;
		pre = cur;
		cur = temp;
	}
	return pre;
} 

//  Merge list 
ListNode* merge(ListNode *l1, ListNode *l2){
    
	if(!l1 || !l2){
    
		return !l1 ? l2 : l1;
	}
	ListNode *head = new ListNode;
	ListNode *h = head;
	while(l1 && l2){
    
		if(l1->val < l2->val){
    
			h->next = l1;
			l1 = l1->next; 
		}else{
    
			h->next = l2;
			l2 = l2->next;
		} 
		h = h->next;
	}
	if(l1){
    
		h->next = l1;
	}
	if(l2){
    
		h->next = l2;
	}
	return head->next;
} 

ListNode* sortOddEvenList(ListNode *head){
    
	if(!head || !head->next){
    
		return head;
	}
	pair<ListNode*, ListNode*> res = partition(head);
	ListNode *odd = res.first;
	ListNode *even = res.second;
	even = reverseLink(even);
	head = merge(odd, even);
	return head;
}

int main(){
    
	ListNode *head, *res;
	create(head);
	head = head->next;
	res = sortOddEvenList(head);
	while(res){
    
		cout<<res->val<<" ";
		res = res->next;
	}
	return 0;
}