引言

大家好啊，我是前端拿破轮😁。

跟着卡哥学算法有一段时间了，通过代码随想录的学习，受益匪浅，首先向卡哥致敬🫡。

但是在学习过程中我也发现了一些问题，很多当时理解了并且AC的题目过一段时间就又忘记了，或者不能完美的写出来。根据费曼学习法，光有输入的知识掌握的是不够牢靠的，所以我决定按照代码随想录的顺序，输出自己的刷题总结和思考。同时，由于以前学习过程使用的是JavaScript,而在2025年的今天，TypeScript几乎成了必备项，所以本专题内容也将使用TypeScript，来巩固自己的TypeScript语言能力。

题目信息

两两交换链表中的节点

leetcode题目链接

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

题目分析

本题考查对链表的基本操作，两两交换链表中的节点，这里要注意的是，我们要进行的是节点的交换，而不是节点的值的交换。不能通过修改节点的值来完成，而是需要通过调整节点间指针的指向关系，让相邻的节点互换。

对于本题，同样有递归和迭代两种实现方式。两种方式的优缺点可以参考上一期内容【代码随想录刷题总结】leetcode206-反转链表

题解

迭代法

对于迭代法，由于在过程中会涉及到对头结点位置的移动，所以使用虚拟头结点来保证对节点操作的一致性。

迭代法通常需要使用指针进行遍历，需要牢记一点，在单链表中，要想操作某一个节点，当前指针必须指向其前一个节点。

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
32
33
34
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function swapPairs(head: ListNode | null): ListNode | null {
    // 剪枝
    if (!head || !head.next) return head;

    const dummy = new ListNode(0, head);

    // 当前指针
    let cur = dummy;
    while (cur && cur.next && cur.next.next) {
        const node1 = cur.next;
        const node2 = cur.next.next;

        // 改变指向
        node1.next = node2.next;
        node2.next = node1;
        cur.next = node2;

        // 移动指针
        cur = node1;
    }
    return dummy.next;
};

时间复杂度：O(n)，其中n为链表的节点数量。

空间复杂度：O(1)，只使用了常数个指针。

递归法

由于链表的定义具有递归性，所以本题也可以使用递归的方式来解决。

递归三部曲：

  1. 确定参数和返回值：function swapPairs(head: ListNode | null): ListNode | null
  2. 确定终止条件：当head或者head.next为null时，返回head。
  3. 确定单层递归逻辑：在每一层中先将head.next.next为首的链表进行两两交换,然后再将head和head.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
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function swapPairs(head: ListNode | null): ListNode | null {
    // 终止条件
    if (!head || !head.next) return head;

    const newList = swapPairs(head.next.next);

    // 交换前两个
    const next = head.next;

    head.next.next = head;
    head.next = newList;
    return next;
};

时间复杂度：O(n)

空间复杂度：O(n),因为递归法有递归调用栈，深度为n

总结

两两交换链表中的节点，同样有迭代和递归两种方式。迭代的空间复杂度更优，而且更容易理解，但是代码较冗长。在使用迭代法的时候要注意使用虚拟头节点。

递归法的空间复杂度较大，且理解略显困难，但是代码简洁精炼。对于超大规模问题，还是可能会导致栈溢出。

好了，这篇文章就到这里啦，如果对您有所帮助，欢迎点赞,收藏,分享👍👍👍。您的认可是我更新的最大动力。

往期推荐✨✨✨

我是前端拿破轮，关注我，和您分享前端知识，我们下期见！