24.两两交换链表中的结点

一、递归

将新头结点指向第二个结点，第二个结点指向第一个结点，第一个结点指向后面的结点，后面的结点进行递归。

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

二、迭代

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummHead = new ListNode(0);
        dummHead->next = head;
        ListNode* cur = dummHead;
        while(cur->next && cur->next->next)
        {
            ListNode* node1 = cur->next;
            ListNode* node2 = cur->next->next;
            cur->next = node2;
            node1->next = node2->next;
            node2->next = node1;
            cur = node1;
        }
        return dummHead->next;
    }
};