My answer using recursion


  • 3
    W
    class Solution {
    public:
        ListNode *swapPairs(ListNode *head) {
            if(NULL == head || NULL == head->next)
                return head;
            ListNode *p = head;
            ListNode *q = p->next;
            ListNode *k = q->next;
            q->next = p;
            p->next = swapPairs(k);
            return q;
        }
    };

  • 0
    G

    Brilliant and easy to follow.


  • 0
    G

    It's fun to solve things recursively, but if you do, just make sure that you recognize that recursive solutions for linear problems like this are not recommended in practice, because you're creating a stack frame for every element in the list, and for even moderately sized lists, this can cause a stack overflow. It's also not as performant as the iterative solution. For tree's and other structures where you can get a log(n) run-time, recursion is more pragmatic.


  • 0
    M

    Question demands the solution to be constant space. But using recursion of your program this can not be achieved, as stack of function (and hence local pointer members) is created which is O(n).


  • 2

    Your solution have too many temporary variable, please have a look at the follow one:

    class Solution {
    public:
        ListNode *swapPairs(ListNode *head) {
            if (head == NULL || head->next == NULL)
                return head;
            ListNode *result = head->next;
    		head->next = swapPairs(head->next->next);
    		result->next = head;
            return result;
        }
    };

  • 0
    S

    Thanks for your post. However it would be better to share solution with correct code format and elaborated thoughts. Please read the Discuss FAQ for more info. Take a look at good sharing example


  • 0
    H
    This post is deleted!

Log in to reply
 

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