Iterative C++ solution with comments - O(1) space complexity


  • 0
    A
    class Solution {
    public:
        ListNode* swapPairs(ListNode* head)
        {
            if(!head || !head->next)
                return head;
            
            ListNode *curr = head->next; //will always track even nodes
            ListNode *prev = head; //will be the one previous to the current node i.e. will track odd nodes
            ListNode *last = nullptr;//the last swapped node
            
            while(curr)
            {
                ListNode *temp = curr->next;
                curr->next = prev; //normal swap
                prev == head ? head = curr : last->next = curr; //updating the head or connecting the list
                last = prev; //after swapping, previous represents the last swapped node
                last->next = temp; //connecting the last node with the remainder of the list. *This step is important
                prev = temp; //Moving to the next odd node, if there exist one
                curr = temp ? temp->next : nullptr; //Moving to the next even node, if there exist one
                
            }
            
            return head;
            
        }
    };
    

Log in to reply
 

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