递归 两两交换链表中的两个节点 - lifengyu360/lifengyu_first_git_test GitHub Wiki

两两交换链表中的节点 给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

class Solution

{

public:

void  SPair(ListNode* pre, ListNode* cur){
    if (cur == nullptr){
        return;
    }

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

    //第一次循环
    if ((pre == cur)
         &&(pre != nullptr)) {
        //
        ListNode *cur_tmp = cur;
        ListNode *cur_next = cur->next;
        ListNode *tail = cur->next->next;
        cur_tmp->next = tail;
        cur_next->next = cur_tmp;
        SPair(cur_tmp,tail); 
        return;
    }

    ListNode *cur_tmp = cur;
    ListNode *cur_next = cur->next;
    ListNode *tail = cur->next->next;
    cur_next->next = cur_tmp;
    cur_tmp->next = tail;
    pre->next = cur_next;

    SPair(cur_tmp,tail); 
}

ListNode* swapPairs(ListNode* head) {
    if (head == NULL){
        return head;
    }

    if (head->next == nullptr){
        return head;
    }
    //2个节点
    if (head->next->next == nullptr){
        ListNode *tmp  = head->next;
        tmp->next = head; 
        head->next = nullptr;
        return tmp;
    }

    //3或以上的节点
    ListNode *cur_next  = head->next;
    ListNode *tail = cur_next->next;
    cur_next->next = head; 
    head->next = tail;

    SPair(head, tail);
    return cur_next;

}

};