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