递归算法：两两交换链表中的节点 ⚡

Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。

两两交换链表中的节点

题目地址： leetcode-cn.com/problems/sw…

题目描述：

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

示例

输入： head = [1,2,3,4]
输出： [2,1,4,3]
复制代码

输入： head = []
输出： []
复制代码

输入： head = [1]
输出： [1]
复制代码

题目分析

本题的难度并不高，主要考查的点在于递归。但其实对于我来说更像是考查链表的修改。

PS: 一般而言，前端可能很少会使用链表，大多数情况下会使用数组来进行存储，这里简略的讲一下链表和数组存储数据的差异。

链表的数据在内存中位置是离散的，依靠着前后链接的next的形式

这样在查询和修改内容时，数组可以按照当前的arr[index]位置直接完成，但是链表就需要通过next一个接一个找下去，进行查询或者修改。

但是，对于增加或者删除操作，使用链表的效率更高，比如删除某一项，数组中后面的元素都要往前移一位，而链表只要删除这一项，并将这一项前后的元素连接起来就好

下面是一个简单的链表例子

例子：

class Person {
    name: string
    next: Person
    constructor(name: string) { this.name = name; }
}

let person = new Person('张三');
person.next = new Person('李四');
person.next.next = new Person('王五');
// 遍历
let nxt = person
while(nxt) {
    console.log(nxt.name);
    nxt = nxt.next;
}
// 删除中间节点李四
person.next = person.next.next;
console.log(person);  // Person { name: '张三', next: Person { name: '王五' } }
复制代码

说的有点远了，再看本题中，传入的数据是链表，所以具有val和next两种属性，并且不要将其当作数组，传入链表是没有length这些属性的。

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
复制代码

本题需要两两进行交换，那么如果数据交换到后面next为空或者只剩下一个时，就结束交换。所以在一开始传入时要进行判断，链表是否为空，或者只有一个数据，如果符合则直接返回。

我在内部重新定义了一个exchange方法，将数据传入，通过第三者变量item来进行.val和.next.val之间的数据交换，并且如果还可以进行，则递归调用exchange方法

代码

var swapPairs = function(head) {
    if (head == null || head.next == null) {
        return head;
    }
    
    function exchange(head) {
        let item = head.val;
        head.val = head.next.val;
        head.next.val = item;
        // 判断后面是否为空或者只有一个节点
        if (head.next.next && head.next.next.next) {
            exchange(head.next.next)
        } 
    }
    exchange(head)
    return head;
};
复制代码