LeetCode 24. Swap Nodes in Pairs [Medium] [C++] 解題筆記

Given a linked list, swap every two adjacent nodes and return its head.

You may not modify the values in the list's nodes, only nodes itself may be changed.

EX:

        Given 1->2->3->4, you should return the list as 2->1->4->3.

想法:

        這題就基本實作題，可以用 iterative 或是 recursive 的方式實作。

完整程式碼:

解法一(iterative):

class Solution {

public:

    ListNode* swapPairs(ListNode* head) {

        auto dummy = new ListNode(0);

        dummy->next = head;

        auto prev = dummy;

        while (prev->next != NULL && prev->next->next != NULL) {

            auto n1 = prev->next;

            auto n2 = prev->next->next;

            auto next = n2->next;

            n1->next = next;

            n2->next = n1;

            prev->next = n2;

            prev = n1;

        }        

        return dummy->next;

    }

};

解法二(recursive):

class Solution {

public:

    ListNode* swapPairs(ListNode* head) {

        if (head == nullptr || head->next ==nullptr) { return head; }

        ListNode *next = head->next;

        head->next = swapPairs(head->next->next);

        next->next = head;

        return next;

    }

};