[C++] LeetCode : Odd Even Linked List

Question

싱글 링크드 리스트의 헤드가 주어지면 홀수번째 노드를 함께 그룹화한 다음 짝수 번째 노드를 그룹화하여 홀수 그룹의 마지막에 짝수 그룹을 연결한 재 정렬된 리스트를 반환하라.

첫 번째 노드는 홀수로 간주되고, 두 번째 노드는 짝수로 간주된다.

짝수 그룹과 홀수 그룹 모두 내부의 상대적인 순서는 입력에서와 같이 유지되어야 한다는 점에 유의한다.
O(1) 공간 복잡도와 O(n) 시간 복잡도에서 문제를 풀어야 한다.

 

제약사항

• 주어진 리스트의 개수는 최소 0개 최대 10^4개 이다.
• 노드의 값은 최소 -10^6 최대 10^6이다.

---

Solution

가능한 최선의 수행 시간(Best Conceivable Runtime(BCR)

  모든 노들들을 최소 한 번식은 봐야 하기 때문에 O(n)이다.

 

고려사항

1. 노드가 없을 경우
2. 노드의 개수에 따른 끝 부분 연결 처리

---

 

Solution1 - 짝수 연결용 노드 별도로 할당

짝수 번째 노드를 그룹화하기 위한 부분을 별도로 처리하여 연결해준다. 

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if (head == NULL) return NULL;
        ListNode* even_head, * even_dummy, * odd_dummy;
        odd_dummy = head;

        if (head->next) {
            even_head = head->next;
            even_dummy = even_head;
        }

        while (head->next && head->next->next) {
            head->next = head->next->next;
            head = head->next;

            if (even_head->next->next) {
                even_head->next = even_head->next->next;
                even_head = even_head->next;
            }
            else {
                even_head->next = NULL;
            }
        }
        head->next = even_dummy;

        return odd_dummy;
    }
};

• Time complexity : O(n), 각 노드를 한 번만 방문하면 된다.
• Space Complexity : O(1), 포인터를 할 당 한 부분만 필요하다.

출처 : https://leetcode.com/explore/interview/card/top-interview-questions-medium/103/array-and-strings/779/

Explore - LeetCode