链表 - 两两交换链表中的节点 - 《数据结构与算法》

题目
思路分析

题目

题目来源：力扣（LeetCode）

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

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

示例 1：

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

输入：head = []
输出：[]
示例 3：

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

思路分析

递归解法

这道题可以通过递归的方式实现两两交换链表中的节点。

首先我们来看下它的终止条件。如果链表中没有接节点，或者链表中只有一个节点，此时是无法进行交换的，则终止递归。

如果链表中至少有两个节点，那么在两两交换链表中的节点之后，原始链表的头节点变成新链表的第二个节点，原始链表的第二个节点变成新的链表的头节点。

链表中的其余节点的两两交换可以递归地实现。在对链表中的其余节点递归地两两交换之后，更新节点之间的指针关系，即可完成整个链表的两两交换。

我们用 head 表示原始链表的头节点，同时也是新链表的第二个节点，用 newHead 表示新链表的头节点，也就是原始链表的第二个节点，因为是两两交换，那么原始链表中的其余节点的头节点是 newHead.next 。令 head.next = swapPairs(newHead.next)，表示将其余节点进行两两交换，交换后的新的头节点为 head 的下一个节点，然后令 newHead.next = head ，即完成了所有节点的交换，最后返回新的链表的头节点 newHead 。

var swapPairs = function(head) {
    if (!head || !head.next) {
      return head;
  }
  // 新链表的头节点为 原始链表的第二个节点
  const newHead = head.next;
  // swapPairs 将给定的链表中的相邻节点两两交换后返回，返回的是交换完成的链表的头节点
  // 交换后的新的头节点为 head 的下一个节点(即新链表的第3个、第5个、第 2n+1 个节点) (其中 n 为 1)
  head.next = swapPairs(newHead.next);
  // 将原始链表的头节点变为新链表的第二个节点
  newHead.next = head;
  return newHead;
}

迭代解法

1、首先创建一个虚拟头节点 hair，让 hair 的 next 指针域指向链表的头节点：hair.next = head
2、然后定义一个 curr 变量，表示当前到达的节点，初始时令 curr 指向虚拟头节点 hair，每次需要交换的就是 curr 后面的两个节点。
3、对于 curr 后面的两个节点，我们分别用变量node1 和变量node2 表示:
4、node1 和 node2 进行交换后，node2 变成了新的头节点，node1 变成了第二个节点，因此，我们将 curr 所指向的节点的后继指针指向 node2所指向的节点 curr.next = node2 ，然后将 node1 的后继指针指向 node2 所指向节点的下一个节点 node1 = node2.next
5、接下来将 node2 所指向的节点的后继指针指向 node1 所指向的节点
此时变量node1 所指向的节点和 node2所指向的节点完成了交换，我们整理一下链表，如下：
6、接下来，将 curr 变量指向变量 node1 指向的变量，下一组待交换的节点 3 和 4，还是一样，分别使用 node1 和 node2 表示，其中 node1 = curr.next ，node2 = node.next
6、我们同样将 curr 所指向的节点的后继指针指向 node2所指向的节点 curr.next = node2 ，将 node1 所指向的节点的后继指针指向 node2 所指向节点的下一个节点 node1 = node2.next，然后将 node2 所指向的节点的后继指针指向 node1 所指向的节点，此时完成了节点3 和节点4 的交换：
我们整理一下链表，如下：
7、对链表中的其余节点进行两两交换，直到全部节点都被两两交换。两两交换链表中的节点之后，新的链表的头节点是 hair.next，返回新的链表的头节点即可。

var swapPairs = function(head) {
  //创建一个虚拟头节点 hair 
  const hair = new ListNode(0);
  // 将虚拟头节点的后继指针指向 链表的头节点
  hair.next = head;
  // 定义 curr 变量，表示当前到达的节点，初始时令 curr 指向 hair
  let curr = hair;
  while (curr.next !== null && curr.next.next !== null) {
        // 分别用变量node1 和 变量node2 表示需要交换的两个节点
      const node1 = curr.next;
      const node2 = curr.next.next;
        // 将 curr 变量所指向的节点的后继指针指向 node2 所指向的节点
      curr.next = node2;
        // 将 node1 所指向的节点的后继指针指向 node2 所指向节点的后一个节点
      node1.next = node2.next;
        // 将 node2 所指向的节点的后继指针指向 node1 所指向的节点，完成两个节点的交换
      node2.next = node1;
        // 完成了两个节点的交换后，令 curr 指向 node1 所指向的节点，重复上述步骤，完成其余两两节点的交换
      curr = node1;
  }
  // 两两交换链表中的节点之后，新的链表的头节点是 hair.next，返回新的链表的头节点
  return hair.next;
};