LeetCode 328パリティチェーンテーブル

タイトルリンク
https://leetcode-cn.com/problems/odd-even-linked-list/
問題解

自分で書いた

構想は、まず2つのチェーンテーブル(奇数番ノードチェーンテーブルと偶数番ノードチェーンテーブル)を確立し、その後チェーンテーブル全体を遍歴し、尾挿法によってこの2つのチェーンテーブルを構築し、最後に偶数番ノードチェーンテーブルを奇数番ノードチェーンテーブルの末尾に接続すればよい.

時間複雑度は(O(n))、空間複雑度は(O(1))

具体的な考え方はコード注釈

を参照する.

// Problem: LeetCode 328
// URL: https://leetcode-cn.com/problems/odd-even-linked-list/
// Tags: Linked List
// Difficulty: Medium

struct ListNode{
    int val;
    ListNode* next;
};

class Solution{
public:
    ListNode* oddEvenList(ListNode* head) {
        //   0 、1   2      
        if (head == nullptr || head->next == nullptr || head->next->next == nullptr)
            return head;
        //          
        ListNode *oddHead = head, *oddTail = oddHead;
        //          
        ListNode *evenHead = head->next, *evenTail = evenHead;
        //               ，true      ，false      
        bool oddFlag = true;
        //           
        head = head->next->next;
        //     ，                    
        while(head != nullptr){
            if(oddFlag==true){
                oddTail->next = head;
                oddTail = oddTail->next;
            }
            else{
                evenTail->next = head;
                evenTail = evenTail->next;
            }
            oddFlag = !oddFlag;
            head = head->next;
        }
        //                  
        oddTail->next = evenHead;
        evenTail->next = nullptr;
        return oddHead;
    }
};

作者:@臭塩魚
転載は出典を明記してください.https://www.cnblogs.com/chouxianyu/
討論と交流を歓迎します!