LeetCode 1721. Swapping Nodes in Linked List

プログラミング
Page content

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

LeetCode 1721Swapping Nodes in Linked Listを解きました。

設問

与えられたLinked Listの前からk番目の要素と後ろからk番目の要素を入れ替える問題。 Linked Listのサイズが与えられないので、後ろからk番目の要素をどうするかが問題のキモです。

解

一度Linked Listを全て走査すればサイズがわかりますが、2回走査することになるので、なるべく1回で済むように実装しました。 変数leftを前からk番目の要素のポインタ、変数rightを後ろからk番目の要素のポインタとしています。

leftは難しいことはなく、rightはk分ずらしてずらして更新していくことで、所望の要素を得ることができる。

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

class Solution {
   public:
    ListNode* swapNodes(ListNode* head, int k) {
        ListNode *left = nullptr, *right = head;

        int count = 0;
        int r_count = k * -1; // k分ずらしておく
        for (ListNode* n = head; n != nullptr; n = n->next) {
            if (++count == k) left = n;
            if (++r_count >= 1) right = right->next;
        }

        auto tmp = left->val;
        left->val = right->val;
        right->val = tmp;

        return head;
    }
};