[LeetCode] 328. Odd Even Linked List

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

Odd Even Linked List - LeetCode

Odd Even Linked List - Medium

 

연결리스트가 주어졌을때, 주어진 연결리스트의 짝수 index에 해당하는 노드는 그 노드들끼리, 홀수 index에 해당하는 노드들은 그 노드들끼리 재정렬하는 문제다. head가 짝수 index이므로 짝수 노드들이 먼저 나와야하며 그 외 순서는 본래 연결리스트와 같아야 한다.

O(1)의 공간복잡도와 O(n)의 시간복잡도가 제한조건으로 주어졌다.

 

[1,2,3,4,5]

 

먼저 tail 포인터를 만들어 제일 뒤 노드를 가리키게 하고, first 포인터를 만들자.

 

tail = 5

first = NULL

 

그 다음 head 부터 시작하여 head->next에 해당하는 노드를 tail->next로 보내주자.

이때 first에 처음으로  head->next에 해당하는 노드를 저장하자.

그러면서 head->next = head->next->next 로 그 다음 노드를 가리키게 하고,

tail = tail->next, tail->next = NULL 로 바꿔주자.

 

[1,3,4,5,2]

head = 1

tail = 2

first = 2

 

그런뒤 head = head->next를 해주자

[1,3,4,5,2]

head = 3

tail = 2

first = 2

 

이제 위 과정을 반복해주는데, head == first 이거나 head->next==first 가 되면 break 해주면 된다.

전체 리스트를 한번씩 훑으므로 O(n) 시간복잡도이고,

tail과 first 두 포인터만 사용하였으므로 O(1)의 공간복잡도를 사용한다.

 

전체 풀이 코드

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if (!head) return head;
        ListNode* tail = head, *root = head;
        ListNode* first=NULL;
        while (tail->next) tail = tail->next;
        while (head->next) {
            if (first && (first==head || first==head->next)) break;
            else {
                first = first? first:head->next;
                tail->next = head->next;
                tail = tail->next;
                head->next = head->next->next;
                tail->next=NULL;
            }
            head = head->next;
        }
        return root;
    }
};