연결 리스트를 홀수 노드 다음에 짝수 노드가 오도록 재구성하라. 공간 복잡도 O(1), 시간 복잡도 O(n)에 풀이하라.
Input: head = [1,2,3,4,5]
Output: [1,3,5,2,4]
Input: head = [2,1,3,5,6,4,7]
Output: [2,3,6,7,1,5,4]
Constraints:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
private:
ListNode* rhead;
ListNode* rtail;
public:
Solution()
{
rhead = NULL;
rtail = NULL;
}
void addNode(int val);
//answer
ListNode* oddEvenList(ListNode* head) {
vector<int> vEven;
bool isOdd = false;
ListNode* tail;
if(head == NULL) return head;
addNode(head->val);
while (head->next != NULL)
{
if (isOdd)
{
addNode(head->next->val);
isOdd = false;
}
else
{
vEven.emplace_back(head->next->val);
isOdd = true;
}
head->next = head->next->next;
}
for (int b : vEven) addNode(b);
return rhead;
}
};
void Solution::addNode(int val)
{
ListNode* temp = new ListNode;
temp->val = val;
temp->next = NULL;
if (rhead == NULL)
{
rhead = temp;
rtail = temp;
}
else
{
rtail->next = temp;
rtail = temp;
}
}
Runtime 12 ms / Memory 11.1 MB
https://leetcode.com/problems/odd-even-linked-list/submissions/925083575/