LeetCode 24. Swap Nodes in Pairs

プログラミング
Page content

どうも、たくチャレ(@takuchalle)です。

LeetCode 24Swap Nodes in Pairsを解きました。

設問

与えられたListed Listを2要素ずつスワップしていく問題。valを書き換えることは禁止で、ポインタのつけかえでのみ入れ替える必要があります。

解

まず、スワップするために必要な要素数に足りない場合は、そのまま返します。要素数が0または1の時がそれにあたります。

その後は2要素ごとにスワップしていきます。ポイントとしてはスワップする2要素だけが影響するのではなく、その前のノードのnextも付け替える必要があるので、prev変数で制御しています。

計算量はO(N)で、消費メモリはO(1)になります。

class Solution {
   public:
    ListNode* swapPairs(ListNode* head) {
        if (head == nullptr) return nullptr;
        if (head->next == nullptr) return head;

        ListNode* p = head->next; // 戻り値用に保存しておく
        ListNode* prev = nullptr;
        for (ListNode* node = head; node != nullptr; node = node->next) {
            if (node->next) {
                ListNode* next = node->next;
                node->next = next->next;
                next->next = node;
                if (prev != nullptr) {
                    prev->next = next;
                }
                prev = node;
            }
        }

        return p;
    }
};