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

[Geekhyt]

原题链接

链表基础知识

数组想必大家都很熟悉，几乎我们每天都会操作它，我们可以对比数组来学习链表。

首先要明确的是，链表和数组的底层存储结构不同，数组要求存储在一块连续的内存中，而链表是通过指针将一组零散的内存块串联起来。可见链表对内存的要求降低了，但是随机访问的性能就没有数组好了，需要 O(n) 的时间复杂度。

下图中展示了单链表及单链表的添加和删除操作，其实链表操作的本质就是处理链表结点之间的指针。

在删除链表结点的操作中，我们只需要将需要删除结点的前驱结点的 next 指针，指向其后继即可。这样，当前被删除的结点就被丢弃在内存中，等待着它的是被垃圾回收器清除。

为了更便于你理解，链表可以类比现实生活中的火车，火车的每节车厢就是链表的一个个结点。车厢之间相互连接，可以添加或者移除掉。春运时，客运量比较大，列车一般会加挂车厢。

链表的结点结构由数据域和指针域组成，在 JavaScript 中，以嵌套的对象形式实现。

{
    // 数据域
    val: 1,
    // 指针域
    next: {
        val:2,
        next: ...
    }
}  

回到本题，先明确想要交换节点共需要有三个指针进行改变。

1.所以我们需要在链表头部添加一个哨兵节点
2.循环中首先操作三个指针完成节点交换
3.指针右移，进行下一对节点的交换

迭代 + 哨兵节点

const swapPairs = (head) => {
  const dummy = new ListNode(0);
  dummy.next = head; // 头部添加哨兵节点
  let prev = dummy;

  while (head && head.next) {
    const next = head.next; // 保存 head.next
    head.next = next.next;
    next.next = head;
    prev.next = next;
    // 下面两个操作将指针更新
    prev = head;      
    head = head.next;
  }
  return dummy.next;
};

• 时间复杂度：O(n)
• 空间复杂度：O(1)

递归

如果你对递归还觉得掌握的不够透彻，可以移步我的这篇专栏 你真的懂递归吗？

回到本题的递归解法：

1.写递归解法的话，老套路，先明确终止条件，链表中没有节点或只有一个节点时无法进行交换。
2.接下来递归的进行两两交换节点并更新指针关系。
3.返回新链表的头节点 newHead。

const swapPairs = function (head) {
    // 递归终止条件
    if (head === null || head.next === null) {
        return head;
    }
    // 获得第 2 个节点
    let newHead = head.next;
    // 将第 1 个节点指向第 3 个节点，并从第 3 个节点开始递归
    head.next = swapPairs(newHead.next);
    // 将第 2 个节点指向第 1 个节点
    newHead.next = head;
    return newHead;
}

• 时间复杂度：O(n)
• 空间复杂度：O(n)