【leetcode】24-两两交换链表中的节点【C++】

题目如下：

解题思路：

方法一：暴力求解，每次交换分情况处理（超时）：

当前待交换的两个节点后续仍有两个及以上节点；当前待交换的两个节点后续只有最后一个节点；当前待交换的两个节点后续没有节点。

代码如下：

/** * 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 == NULL || head->next == NULL) return head; ListNode *res = head->next; while(head && head->next){ //后续仍有两个及以上节点 if(head->next->next && head->next->next->next){ ListNode *temp = head->next->next; head->next = head->next->next->next; head->next->next = head; head = temp; } else if(head->next->next){ //后续只有最后一个节点 head->next = head->next->next; head->next->next = head; break; } else{ //后续无任何节点 head->next->next = head; head->next = NULL; break; } } return res; } };

方法二：递归求解，递归终止的条件是：

当前待交换的两个节点中一个为空当前待交换的两个节点均为空。

代码如下：

/** * 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 == NULL || head->next == NULL) //递归终止 return head; ListNode *res = head->next; ListNode *temp = head->next->next; head->next->next = head; head->next = swapPairs(temp); //递归调用 return res; } };