True constant space C++ solution, no recursion, no dummy nodes.


  • 0
    Z

    If you need to modify the next field then simply use ListNode ** and every thing will be solved smoothly (providing the performance is not the issue).

    In this case you only need swap three next fields and that's all.

    class Solution {
    public:
        ListNode* swapPairs(ListNode* head) {
            ListNode **fst = &head;
            while (*fst && (*fst)->next) {
                ListNode **snd = &(*fst)->next;
                ListNode **thd = &(*snd)->next;
                
                ListNode *tmp = *fst;
                *fst = *snd;
                *snd = *thd;
                *thd = tmp;
                
                fst = snd;
            }
            return head;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.