NC207. 排序奇升偶降链表
描述
示例1
输入:
{1,3,2,2,3,1}
输出:
{1,1,2,2,3,3}
示例2
输入:
{1,2,2}
输出:
{1,2,2}
C 解法, 执行用时: 8ms, 内存消耗: 1384KB, 提交时间: 2021-11-21
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*
* C语言声明定义全局变量请加上static，防止重复定义
*/
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类
* @return ListNode类
*/
struct ListNode* sortLinkedList(struct ListNode* head ) {
// write code here
struct ListNode* firstList = NULL;
struct ListNode* firstPoint = NULL;
struct ListNode* secondList = NULL;
struct ListNode* secondPoint = NULL;
int cnt = 1;
struct ListNode* temp = NULL;
while( head != NULL ) {
temp = head;
head = head->next;
if( cnt % 2 == 1 ) {
if( firstList == NULL ) {
firstList = firstPoint = temp;
} else {
firstPoint->next = temp;
firstPoint = temp;
}
firstPoint->next = NULL;
} else {
if( secondList == NULL ) {
secondList = secondPoint = temp;
secondPoint->next = NULL;
} else {
temp->next = secondList;
secondList = temp;
}
}
cnt++;
}
struct ListNode* result = NULL;
struct ListNode* p = NULL;
while( firstList != NULL || secondList != NULL ) {
if( firstList == NULL ) {
if( result == NULL ) {
result = secondList;
} else {
p->next = secondList;
}
return result;
}
if( secondList == NULL ) {
if( result == NULL ) {
result = firstList;
} else {
p->next = firstList;
}
return result;
}
struct ListNode* temp = NULL;
if( firstList->val < secondList->val ) {
temp = firstList;
firstList = firstList->next;
} else {
temp = secondList;
secondList = secondList->next;
}
if( result == NULL ) {
result = p = temp;
p->next = NULL;
continue;
}
p->next = temp;
p = temp;
p->next = NULL;
}
return result;
}
C++ 解法, 执行用时: 8ms, 内存消耗: 1388KB, 提交时间: 2022-03-08
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类
* @return ListNode类
*/
// 拆分两个链表
// 反转偶链表
// 归并排序
// 反转链表
ListNode* reverseList(ListNode* head){
ListNode *pre=nullptr,*cur=head;
while(cur){
ListNode *tmp=cur->next;
cur->next=pre;
pre=cur;
cur=tmp;
}
return pre;
}
ListNode* mergeList(ListNode *head1,ListNode *head2){
ListNode *dummy=new ListNode(-1);
ListNode *p1=head1,*p2=head2;
ListNode *cur=dummy;
while(p1&&p2){
if(p1->val<=p2->val){
cur->next=p1;
p1=p1->next;
}else{
cur->next=p2;
p2=p2->next;
}
cur=cur->next;
}
cur->next= p1?p1:p2;
return dummy->next;
}
ListNode* sortLinkedList(ListNode* head) {
// write code here
ListNode *head1=new ListNode(-1);
ListNode *head2=new ListNode(-1);
auto p1=head1,p2=head2;
auto cur=head;
int pos=0;
// 拆分
while(cur){
if(pos%2==0){
p1->next=cur;
p1=p1->next;
}else{
p2->next=cur;
p2=p2->next;
}
++pos;
cur=cur->next;
}
p1->next=nullptr;
p2->next=nullptr;
// 反转
head2=head2->next;
head1=head1->next;
head2=reverseList(head2);
// 归并
head=mergeList(head1, head2);
return head;
}
};
C++ 解法, 执行用时: 8ms, 内存消耗: 1388KB, 提交时间: 2022-02-09
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {
public:
/*
方法一：三步走
直接对链表进行排序的话至少也需要O(nlogn)的时间复杂度，我们注意到链表的奇数位和偶数位其实是有序的，
而要将两个有序的部分变为整体有序，归并是再适合不过的了。因此我们可以按照如下的算法来求解：
1. 先将链表的拆成奇数位和偶数位两条链表，时间复杂度O(n)；
2. 再将偶数位链表进行反转，时间复杂度O(n)；
3. 最后归并两个升序的链表，时间复杂度O(n)。
算法的整体时间复杂度是O(n)，只使用了有限几个变量，空间复杂度为O(1)。
*/
ListNode* sortLinkedList(ListNode* head) {
if(head == NULL || head->next == NULL) return head;
//先把奇数位链表和偶数位链表拆开
ListNode* oddCur = head;
ListNode* evenCur = oddCur->next;
ListNode* oddHead = oddCur;
ListNode* evenHead = evenCur;
while(evenCur != NULL){
oddCur->next = evenCur->next;
if(oddCur->next != NULL)
evenCur->next = oddCur->next->next;
oddCur = oddCur->next;
evenCur = evenCur->next;
}
//然后把偶数位链表逆序
evenHead = reverseList(evenHead);
//最后把两个升序的链表归并
return mergeList(oddHead, evenHead);
}
private:
// 反转链表
ListNode* reverseList(ListNode* head) {
if(head == NULL) return head;
ListNode* prev = NULL;
ListNode* cur = head;
while(cur != NULL){
ListNode* next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
return prev;
}
// 合并两个有序链表
ListNode* mergeList(ListNode* head1, ListNode* head2) {
ListNode* dummy = new ListNode(-1);
ListNode* cur = dummy;
while(head1 != NULL && head2 != NULL){
if(head1->val <= head2->val){
cur->next = head1;
head1 = head1->next;
}
else{
cur->next = head2;
head2 = head2->next;
}
cur = cur->next;
}
while(head1 != NULL){
cur->next = head1;
head1 = head1->next;
cur = cur->next;
}
while(head2 != NULL){
cur->next = head2;
head2 = head2->next;
cur = cur->next;
}
return dummy->next;
}
};
C++ 解法, 执行用时: 8ms, 内存消耗: 1412KB, 提交时间: 2022-03-13
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类
* @return ListNode类
*/
ListNode* sortLinkedList(ListNode* head) {
// write code here
if (head == nullptr || head->next == nullptr) return head;
// 拆分奇偶链表
ListNode* head1 = head, *head2 = head->next;
ListNode* l1 = head1, *l2 = head2;
while (l2 && l2->next) {
l1->next = l2->next; // 四步曲
l2->next = l1->next->next;
l1 = l1->next;
l2 = l2->next;
}
// 奇链表: head1, 偶链表: head2
l1->next = nullptr; // 这一步千万不能遗漏掉
// 反转偶数链表
head2 = reverseLinkedList(head2);
// 合并两个有序链表
return mergeLinkedList(head1, head2);
}
ListNode* mergeLinkedList(ListNode* head1, ListNode* head2) {
ListNode* dummy = new ListNode(0);
ListNode* prev = dummy, *l1 = head1, *l2 = head2;
while (l1 && l2) {
if (l1->val <= l2->val) {
prev->next = l1;
prev = l1;
l1 = l1->next;
} else {
prev->next = l2;
prev = l2;
l2 = l2->next;
}
}
while (l1) {
prev->next = l1;
prev = l1;
l1 = l1->next;
}
while (l2) {
prev->next = l2;
prev = l2;
l2 = l2->next;
}
return dummy->next;
}
ListNode* reverseLinkedList(ListNode* head) {
if (head == nullptr || head->next == nullptr) return head;
ListNode* prev = nullptr, *cur = head;
while (cur) {
ListNode* next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
return prev;
}
};
C++ 解法, 执行用时: 8ms, 内存消耗: 1416KB, 提交时间: 2022-01-27
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类
* @return ListNode类
*/
ListNode* sortLinkedList(ListNode* head) {
// write code here
ListNode* odd=new ListNode(0);
ListNode* even=new ListNode(0);
ListNode* list_odd=odd;
ListNode* list_even=even;
while(head && head->next) {
list_odd->next=head;
head=head->next;
list_odd=list_odd->next;
list_even->next=head;
head=head->next;
list_even=list_even->next;
}
if(head) {
list_odd->next=head;
list_odd=list_odd->next;
}
list_odd->next=nullptr;
list_even->next=nullptr;
even=reverse(even->next);
odd=odd->next;
return Merge(odd, even);
}
ListNode* reverse(ListNode* need) {
ListNode* last=nullptr;
ListNode* front=need;
ListNode* next=need;
if(!need || !need->next)
return need;
while(front) {
next=next->next;
front->next=last;
last=front;
front=next;
}
return last;
}
ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
ListNode* list1 = pHead1;
ListNode* list2 = pHead2;
ListNode* list1_pre = pHead1;
while(list1&&list2){
if(list1->val >= list2->val){
if(list1 == pHead1){
ListNode* tmp = list2->next;
list2->next = list1;
pHead1 = list2;
list2 = tmp;
list1_pre = pHead1;
}
else{
ListNode* tmp = list2->next;
list2->next = list1;
list1_pre->next = list2;
list2 = tmp;
list1_pre = list1_pre->next;
}
}
else{
if(list1 == pHead1)
list1 = list1->next;
else{
list1 = list1->next;
list1_pre = list1_pre->next;
}
}
}
if(list2 == NULL)
return pHead1;
else{
list1_pre->next = list2;
return pHead1;
}
}
};