문제 링크. O(n) 시간과 O(1) 공간으로 해결해보자.

Input:  1->2->3->4->5->null
Output: 1->3->5->2->4->null

홀수 리스트와 짝수 리스트를 분리한 다음 둘을 연결하는 것으로 쉽게 해결할 수 있다: 홀수 리스트와 짝수 리스트는 포인터를 두 칸씩 전진하면 구할 수 있다. 이렇게 분리한 두 리스트를, 미리 저장해두었던 짝수 리스트의 첫 원소 포인터를 이용해 붙여주면 끝!

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
struct Solution {
    ListNode* oddEvenList(ListNode * head) {
        if (head == nullptr) return nullptr; // 빈 리스트가 들어올 수 있다.
        auto * odd  = head;
        auto * even = head -> next;
        auto * conn = even;
        while (odd -> next != nullptr && even -> next != nullptr) {
            auto * odd_next  = odd  -> next -> next;
            auto * even_next = even -> next -> next;
            odd  -> next = odd_next;
            even -> next = even_next;
            odd  = odd  -> next;
            even = even -> next;
        }
        odd -> next = conn;
        return head;
    }
};