Odd Even Linked List

328. Odd Even Linked List

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

Odd Even Linked List - LeetCode

 Language: C++

time: O(n), space: O(1)

/**
 * 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) {
            ListNode* odd = head;
            ListNode* even = head->next;
            ListNode* evenHead = even;
            
            while (even != NULL && even->next != NULL) {
                odd->next = even->next;
                odd = odd->next;
                even->next = odd->next;
                even = even->next;
            }
            odd->next = evenHead;
        }
        return head;
    }
};

이게 더 이해하기 쉽기도 하고 런타임은 빠르다

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if(!head) return NULL;
        ListNode* odd = head;
        ListNode* evenHead = head->next;
        ListNode* even = evenHead;
        
        while(odd->next && even->next) {
            odd->next = odd->next->next;
            odd = odd->next;
            even->next = even->next->next;
            even = even->next;
        }
        
        odd->next = evenHead;
        return head;
    }
};

시도

/**
 * 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 && head->next && head->next->next) {
            ListNode* cur = head;
            ListNode* node = cur->next;
            int lastVal = head->next->val;
            do {
                node = cur->next;
                cur->next = node->next;
                ListNode* temp = cur->next;
                node->next = NULL;
                while(temp->next != NULL) {
                    temp = temp->next;
                }
                temp->next = node;
                cur = cur->next;
            } while (cur->val != lastVal && cur->next->val != lastVal);
            
        }
        return head;
    }
};

문제점

접근 방식이 나는 그냥 원래 리스트에서 노드의 값이 다 다르다는 전제 하에 두번째 노드를 다시 만났을 때 멈추기로 했었는데

솔루션은 Odd Linked List, Even Linked List 이렇게 두 개를 만들어 놓고 진행했다.

Odd Linked List 에서 짝수 번째에 있는 것을 Even Linked List 로 이동시킨 후 null을 만났을 때 합체시켜주는 방식이었다.