24. 两两交换链表中的节点

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

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

示例 1：

day8.[链表].24. 两两交换链表中的节点 - 图1

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

示例 2：

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

示例 3：

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

提示：

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

思路

使用递归。

先判断边界条件，如果链表的长度少于 2，直接返回。

1、每次遍历两个节点

2、交换两个节点的 next 的值

3、遍历之后的节点

代码

var swapPairs = function(head) {
    if (!head || !head.next) return head;
    const tmp = head.next;
    head.next = swapPairs(tmp.next)
    tmp.next = head;
    return tmp;
};

复杂度分析

时间复杂度 day8.[链表].24. 两两交换链表中的节点 - 图2#card=math&code=O%28N%29)

空间复杂度 day8.[链表].24. 两两交换链表中的节点 - 图3#card=math&code=O%28N%29)