CodeTop - 排序奇升偶降連結清單

題目

代碼

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

/*
給定一個奇數位升序，偶數位降序的連結清單，将其重新排序（升序）
例：1->8->3->6->5->4->7->2->NULL
	1->2->3->4->5->6->7->8->NULL
	
解法：
	1）首先安裝奇偶順序将連結清單進行拆分（1->3->5->7->NULL和8->6->4->2->NULL) 
	2）反轉偶連結清單(1->3->5->7->NULL和2->4->6->8->NULL)
	3）合并兩個連結清單 
*/

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<ListNode*, ListNode*> 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<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;
}