CodeTop - 排序奇升偶降链表

#include 
#include 
using namespace std; 



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;
	}
}

// 拆分奇偶链表 
pair partition(ListNode *head){
	// 奇链表初始化 
	ListNode *oddhead = new ListNode;
	oddhead->next = NULL;
	ListNode *oddtail = oddhead;
	// 偶链表初始化 
	ListNode *evenhead = new ListNode;
	evenhead->next = NULL;
	ListNode *eventail = evenhead;
	int i = 1;  // 记录链表顺序
	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};
}

// 反转链表
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;
} 

// 合并链表
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 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<val<<" ";
		res = res->next;
	}
	return 0;
}