Given a linked list, swap every two adjacent nodes and return its head.
You may not modify the values in the list’s nodes, only nodes itself may be changed.
Example:
Given 1->2->3->4, you should return the list as 2->1->4->3.
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/swap-nodes-in-pairs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
想要采用递归解法, 首先思考这几个问题:
1) 原始问题能否划分为若干个相同的子问题
2) 递归的结束条件是什么
3) 递归的调用条件
对于本题:
子问题: 需要两两一组地将链表反转, 可以将原问题划分为简单的若干子问题(绿框), 每个子问题的操作就是仅有的两个结点反转, 修改指针即可(蓝线).
结束条件: 当子问题中不足两个结点时, 无法完成反转, 此时递归跳出.
调用条件: 需要将各个子问题中反转的链表连接起来, 对于每个子问题的头节点, 在反转之后变成尾结点, 即第一个子问题的尾结点需要指向下一个子问题的头节点(红线), 即递归调用的结果.
C++:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20/**
* 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 *next = head -> next;
head -> next = swapPairs(next -> next);
next -> next = head;
return next;
}
};