给定一个单链表,请设定一个函数,将链表的奇数位节点和偶数位节点分别放在一起,重排后输出。
注意是节点的编号而非节点的数值。
#include<iostream>
#include<stack>
using namespace std;
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
class Solution {
public:
ListNode* oddEvenList(ListNode* head) {
// write code here
stack<int> stack_odd;
stack<int> stack_even;
//准备两个stack容器,一个放奇数,一个放偶数
stack<int> stack_answer;
ListNode* p = head;
if (!head || !head->next){
return head;
}
ListNode *p1 = head;
while (p1){
stack_odd.push(p1->val);
if (p1->next){
p1 = p1->next;
}
else{
break;
}
stack_even.push(p1->val);
if (p1->next){
p1 = p1->next;
}
else{
break;
}
}
while (stack_even.size()){
stack_answer.push(stack_even.top());
stack_even.pop();
}
while (stack_odd.size()){
stack_answer.push(stack_odd.top());
stack_odd.pop();
}
while (stack_answer.size()){
p->val = stack_answer.top();
stack_answer.pop();
p = p->next;
}
return head;
}
}
时间复杂度O(n)