Simple 0ms c++ solution(beats 98.08%)


  • 5
    1

    All we need to do is rearrange the links in the list.If prev is the pevious node, head is the current node,at every alternate node perform operations such that

    Initial: prev | head | head->next|head->next->next
    After swap:prev|head->next|head|head->next->next

     ListNode* swapPairs(ListNode* head) {
            ListNode* dummy=new ListNode(0);
            dummy->next=head;
            ListNode* prev=dummy;
            while(head &&head->next)
            {
                ListNode* nn=head->next->next;
                prev->next=head->next;
                head->next->next=head;
                head->next=nn;
                prev=head;
                head=nn;
               
            }
            return dummy->next;
            
        }
    

  • 0

    @vk1993 Nice solution and good explanation. Have fun in Leetcode.


  • 0
    1

    @LHearen Thank you.


  • 0
    Q

    @vk1993 memory leak?


  • 0

    @qlin ? It's ACed easily. What's the exact problem you mentioned here?


  • 0
    Q

    @LHearen He new the ListNode, but not delete it.


  • 0

    @qlin Actually in the OJ, right now. We will not consider the garbage collection problem, so this cannot be the real problem.


  • 2
    L
    ListNode* swapPairs(ListNode* head) {
           ListNode **p = &head, *ptr = NULL;
           while ((*p) && (*p)->next) {
               ptr = (*p)->next->next;
               (*p)->next->next = (*p);
               (*p) = (*p)->next;
               (*p)->next->next = ptr;
               p = &((*p)->next->next);
               
           }
           return head;
       }
    

    Using pointer to pointer to save dummy and return head.


  • 0
    Q

    You do have memory leak issue. In an interview, this could make you fail. However, it is easy to fix: just create ListNode dummy; and use dummy.next = head; ListDode* prev = &dummy;
    On the other hand, the **p technique that leaper showed is a more advanced way which Mr. Linuz used in Linux kernel, and we all should learn.


  • 0
    S

    It's a brilliant answer!!!


Log in to reply
 

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