Odd Even Linked List

링크드 리스트의 헤드 포인터를 받고 해당

리스트의 홀수번째 노드들과 짝수번째 노드들을 나누고,

홀수 번째 노드 리스트 뒤에 짝수번째 노드 리스트들이 있도록 재구축하는 문제

You must solve the problem in O(1) extra space complexity and O(n) time complexity.

위와 같은 알고리즘의 시공간 조건이 존재한다.

/**
 * 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 {
public:
    ListNode* oddEvenList(ListNode* head) {

        if (head == NULL || head->next == NULL)
        {
            return head;
        }

        ListNode *oddHead{head};
        ListNode *evenHead{head->next};
        ListNode *even{evenHead};
        ListNode *odd{oddHead};

        while (even != NULL)
        {
            odd->next = even->next;

            if (odd->next == NULL)
            {
                break;
            }

            odd = odd->next;

            even->next = odd->next;
            even = even->next;
        }

        odd->next = evenHead;

        return oddHead;
    }
};