/*
 * @author:leacoder
 * @des: 迭代实现 两两交换链表中的节点
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        /*在头节点前 新建一节点，其next指向head。好处 将[]\[1]这种特殊情况能够统一处理*/
        ListNode *virtualnode = new ListNode(0);
        virtualnode->next = head;
        
        ListNode *node = virtualnode;//存储新的开始节点
        
        while(head&&head->next){
            ListNode *tmp = head->next;//不变的 
            head->next = tmp->next;
            tmp->next = head;//交换
            node->next = tmp;
            
            node = head;
            head = node->next;//下移
        }
        
        return virtualnode->next;
            
    }
};

/**
 * @author:leacoder
 * @des: 递归实现 两两交换链表中的节点
 */
class Solution {
public:
    //每两个节点为一组  反转前的前节点（反转后的 后节点）、反转前的后节点（反转后的 前节点）
    //下一组 为 反转前的后节点（反转后的 前节点）的 next 以及 next.next
    ListNode* swapPairs(ListNode* head) { //入参 反转前的前节点（反转后的 后节点）
        ////传入的参数的合法性，递归的终止条件
        if (NULL==head || NULL==head->next) 
            return head; 
        ListNode *res = head->next; //记录 反转前的后节点（反转后的 前节点）
        head->next = swapPairs(res->next); //更新 反转后的 后节点 的next  为下一组 反转后的 前节点  （入参为反转前的后节点的next 即为下一组的 反转前的前节点（反转后的 后节点）
        res->next = head; //更新 反转后的 前节点的next 为 反转前 的 前节点
        
        return res;
    }
};