两两交换链表中的节点

节点"/>

两两交换链表中的节点

目录

1. 分析题意

2. 分析算法原理

2.1. 递归思路：

1. 挖掘子问题

3. 编写代码

3.1. step 1：

3.2. step 2：

3.3. step 3：

3.4. 递归代码

1. 分析题意

力扣上原题链接如下：

24. 两两交换链表中的节点 - 力扣（LeetCode） 

给一个单链表，让我们两两交换相邻的节点，并返回交换后链表的头节点。

注意：不可以修改原节点内部的val，只能进行节点交换。

2. 分析算法原理

2.1. 递归思路：

如果一个问题可以用递归的方案解决，那么首先我们需要挖掘出重复的子问题。

上面的问题的目的，两两进行交换相邻的节点，并返回交换后的头节点。例如：

1. 挖掘子问题

如果我要进行两两交换相邻的节点，那么我们可以先把 1，2看成一个整体，此时我们就需要先进行交换3，4，这两个相邻的节点。例如：

同理，如果3、4这两个节点后面还有两个以上的节点，那么就继续把3、4看成一个整体，重复上述操作。但如果后面的节点个数为1或0，那么就停止交换，并返回自身即可，例如上面，此时只有5这个节点，返回5这个节点即可。 

此时我们就发现了重复的子问题：当后面的节点个数大于2时，就两两交换相邻的节点，并返回交换后的头节点。

3. 编写代码

3.1. step 1：

步骤一：重复子问题，该过程决定了递归函数函数头的设计。经过我们上面的分析，重复子问题就是两两交换相邻的节点。

// 函数头:
Node* dfs(node);

3.2. step 2：

步骤二：只关心某一个子问题在做什么事情，这个过程决定了函数体的设计。

对于递归代码的编写，我们需要站立在宏观角度看待递归问题，我们一定要相信上面的dfs这个递归函数一定可以达到我们的预期：交换两两相邻的节点，并返回交换后的头结点。

// 函数体:
// 交换逻辑
tmp = dfs(node->next->next);
node->next->next = node;
ret = node->next;   // 保存交换后的头节点
node->next = tmp;
// 返回交换后的头节点
return ret;

3.3. step 3：

step three：当一个问题不可以在被分为相同子问题的时候，就是递归结束条件；这个过程决定了递归的出口；

那么上面的结束条件就是：当遇到空节点或者叶子节点，那就不需要在交换了，此时只需要返回自身即可。

if( !node || !(node->next)) return node;

3.4. 递归代码

class Solution {
public:ListNode* swapPairs(ListNode* head) {// 遇到空节点 or 遇到了叶子节点,那么就不要在交换了if(!head || !(head->next))  return head;// 交换head->next->next 和 head->next->next->next这两个节点// 并 return 交换后的头节点ListNode* Node = swapPairs(head->next->next);head->next->next = head;ListNode* ret = head->next;  // 提前保存一下交换后的头节点head->next = Node;return ret;}
};