[LeetCode]홀짝 연결 리스트

문제

연결 리스트를 홀수 노드 다음에 짝수 노드가 오도록 재구성하라. 공간 복잡도 O(1), 시간 복잡도 O(n)에 풀이하라.

예제

• Example 1:
  

Input: head = [1,2,3,4,5]
Output: [1,3,5,2,4]

• Example 2:
  

Input: head = [2,1,3,5,6,4,7]
Output: [2,3,6,7,1,5,4]

Constraints:

• The number of nodes in the linked list is in the range [0, 104].
• -106 <= Node.val <= 106

코드

/**
 * 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/

---

https://leetcode.com/problems/odd-even-linked-list/