24. Swap Nodes in Pairs

recursive O(n) time O(n) space

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        curr = head.next
        succ = self.swapPairs(curr.next)
        curr.next = head
        head.next = succ
        return curr

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (!head || !head->next) return head;
        auto next = head->next, ret = swapPairs(next->next);
        next->next = head;
        head->next = ret;
        return next;
    }
};

iterative O(n)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        dummy = ListNode(next=head)
        prev, curr = dummy, head
        while curr and curr.next:
            succ = curr.next
            curr.next = succ.next
            succ.next = prev.next
            prev.next = succ
            prev = curr
            curr = curr.next
        return dummy.next

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode dummy_head(0), *prev = &dummy_head, *curr = head;
        dummy_head.next = curr;
        while (curr && curr->next) {
            auto succ = curr->next;
            curr->next = succ->next;
            succ->next = prev->next;
            prev->next = succ;
            prev = curr;
            curr = prev->next;
        }
        return dummy_head.next;
    }
};