Frontend Interview

Appearance

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

题目链接：https://leetcode.cn/problems/swap-nodes-in-pairs/

代码 ​

ts
/**
 * 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 === null || head.next === null){
        return head;
    }
    const next = head.next;
    head.next = swapPairs(next.next);
    next.next = head;
    return next;
};

思路 ​

使用递归方法两两交换链表节点：

  1. 递归终止条件：
    • 如果链表为空或只有一个节点，直接返回 head
  2. 递归处理：
    • 保存 head 的下一个节点 next
    • 递归处理 next.next 之后的链表，将结果连接到 head.next
    • 将 next.next 指向 head，完成交换
    • 返回 next 作为新的头节点

示例 ​

对于链表 1 -> 2 -> 3 -> 4：

  • 交换 1 和 2：2 -> 1 -> ...
  • 递归处理 3 和 4：2 -> 1 -> 4 -> 3

关键点 ​

  • 递归思想：将问题分解为交换前两个节点 + 递归处理剩余部分

  • 每次递归返回交换后的新头节点

  • 递归终止条件处理边界情况

  • 时间复杂度 O(n)，其中 n 是链表的长度

  • 空间复杂度 O(n)，递归调用栈的深度