LeetCode 24. 两两交换链表中的节点【知识点：虚拟表头，迭代，递归】_题目详情 代码提交 运行结果 7 两两交换链表中的节点 作者: turbo时间限制: 1s章

题目

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

输入：head = [1,2,3,4]
输出：[2,1,4,3]

示例 2：

输入：head = []
输出：[]

示例 3：

输入：head = [1]
输出：[1]

提示：

链表中节点的数目在范围 [0, 100] 内
0 <= Node.val <= 100

来源：力扣（LeetCode）
链接: LeetCode 24. 两两交换链表中的节点
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
__________________________________________________________________________________

解题

1. 迭代

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* swapPairs(struct ListNode* head)
{
    struct ListNode dummyHead;
    dummyHead.next = head;

    struct ListNode *rear,*front,*behind;

    rear = &dummyHead;
    while(rear->next && rear->next->next){

        front = rear->next;
        behind = front->next;

        front->next = behind->next;
        behind->next = front;

        rear->next = behind;
        rear = front;
    }

    return dummyHead.next;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

2.递归

struct ListNode* swapPairs(struct ListNode* head)
{
    if(head == NULL || head->next == NULL){
        return head;
    }

    struct ListNode* newHead = head->next;
    head->next = swapPairs( newHead->next );
    newHead->next = head;

    return newHead;
}
1
2
3
4
5
6
7
8
9
10
11
12

__________________________________________________________________________________

知识点进阶

关于递归，转述大神的讲解：

https://lyl0724.github.io/2020/01/25/1/

• 递归解题三部曲

何为递归？程序反复调用自身即是递归。

我自己在刚开始解决递归问题的时候，总是会去纠结这一层函数做了什么，它调用自身后的下一层函数又做了什么…然后就会觉得实现一个递归解法十分复杂，根本就无从下手。

相信很多初学者和我一样，这是一个思维误区，一定要走出来。既然递归是一个反复调用自身的过程，这就说明它每一级的功能都是一样的，因此我们只需要关注一级递归的解决过程即可。

如上图所示，我们需要关心的主要是以下三点：

整个递归的终止条件。
一级递归需要做什么？
应该返回给上一级的返回值是什么？

因此，也就有了我们解递归题的三部曲：

1.找整个递归的终止条件：递归应该在什么时候结束？

2.找返回值：应该给上一级返回什么信息？

3.本级递归应该做什么：在这一级递归中，应该完成什么任务？

一定要理解这3步，这就是以后递归秒杀算法题的依据和思路。

但这么说好像很空，我们来以题目作为例子，看看怎么套这个模版，相信3道题下来，你就能慢慢理解这个模版。之后再解这种套路递归题都能直接秒了。

__________________________________________________________________________________
例1：求二叉树的最大深度

先看一道简单的Leetcode题目：Leetcode 104. 二叉树的最大深度

题目很简单，求二叉树的最大深度，那么直接套递归解题三部曲模版：

1.找终止条件。 什么情况下递归结束？当然是树为空的时候，此时树的深度为0，递归就结束了。

2.找返回值。 应该返回什么？题目求的是树的最大深度，我们需要从每一级得到的信息自然是当前这一级对应的树的最大深度，因此我们的返回值应该是当前树的最大深度，这一步可以结合第三步来看。

3.本级递归应该做什么。 首先，还是强调要走出之前的思维误区，递归后我们眼里的树一定是这个样子的，看下图。此时就三个节点：root、root.left、root.right，其中根据第二步，root.left和root.right分别记录的是root的左右子树的最大深度。那么本级递归应该做什么就很明确了，自然就是在root的左右子树中选择较大的一个，再加上1就是以root为根的子树的最大深度了，然后再返回这个深度即可。

具体Java代码如下：

class Solution {
    public int maxDepth(TreeNode root) {
        //终止条件：当树为空时结束递归，并返回当前深度0
        if(root == null){
            return 0;
        }
        //root的左、右子树的最大深度
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);
        //返回的是左右子树的最大深度+1
        return Math.max(leftDepth, rightDepth) + 1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

当足够熟练后，也可以和Leetcode评论区一样，很骚的几行代码搞定问题，让之后的新手看的一脸懵逼(这道题也是我第一次一行代码搞定一道Leetcode题)：

class Solution {
    public int maxDepth(TreeNode root) {
        return root == null ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}
1
2
3
4
5

__________________________________________________________________________________
例2：两两交换链表中的节点

直接上三部曲模版：

1.找终止条件。 什么情况下递归终止？没得交换的时候，递归就终止了呗。因此当链表只剩一个节点或者没有节点的时候，自然递归就终止了。

2.找返回值。 我们希望向上一级递归返回什么信息？由于我们的目的是两两交换链表中相邻的节点，因此自然希望交换给上一级递归的是已经完成交换处理，即已经处理好的链表。

3.本级递归应该做什么。 结合第二步，看下图！由于只考虑本级递归，所以这个链表在我们眼里其实也就三个节点：head、head.next、已处理完的链表部分。而本级递归的任务也就是交换这3个节点中的前两个节点，就很easy了。

具体Java代码如下：

class Solution {
    public ListNode swapPairs(ListNode head) {
      	//终止条件：链表只剩一个节点或者没节点了，没得交换了。返回的是已经处理好的链表
        if(head == null || head.next == null){
            return head;
        }
      	//一共三个节点:head, next, swapPairs(next.next)
      	//下面的任务便是交换这3个节点中的前两个节点
        ListNode next = head.next;
        head.next = swapPairs(next.next);
        next.next = head;
      	//根据第二步：返回给上一级的是当前已经完成交换后，即处理好了的链表部分
        return next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15