链表的奇偶重排

给定一个单链表,请设定一个函数,将链表的奇数位节点和偶数位节点分别放在一起,重排后输出。
注意是节点的编号而非节点的数值。

#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)

上一篇:leetcode412


下一篇:[LeetCode] 1847. Closest Room