[LeetCode] 328. Odd Even Linked List

linked list가 들어왔을 때, 홀수번째 노드와 짝수번째 노드를 순서대로 따로 모으고, 홀수번째 노드 리스트 -> 짝수번째 노드 리스트로 출력하라는 문제다.

 

먼저 예외사항을 체크해주고, 그 뒤 flag를 둬서 짝수번째인지 홀수번째인지 구분하면서 각각의 linked list에 연결해주고, 마지막에 홀수 리스트의 next를 짝수 리스트의 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 == NULL) return NULL;
        else if (head->next == NULL) return head;
        
        ListNode* oddhead = head;
        ListNode* evenhead = head->next;
        

        
        ListNode* odd = oddhead;
        ListNode* even = evenhead;
        
        head = head->next->next;

        oddhead->next = NULL;
        evenhead->next = NULL;

        
        int flag = 1;
        
        while (head!= NULL){
            
            if (flag == 1){
                odd->next = head;
                odd = odd->next;
                head = head->next;
                odd->next = NULL;
                flag = 0;
            }
            else{
                even->next = head;
                even = even->next;
                head = head->next;
                even->next = NULL;
                flag = 1;
            }
            
            
        }
        
        
        odd->next = evenhead;
          
        return oddhead;
    }
};