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

解法一：迭代

在做题之前需要分析一下链表有多少种情况：

1. 链表没有元素
2. 链表只有一个元素
3. 链表的元素个数为奇数
4. 链表的元素个数为偶数

当 head 为 null 或者只有一个元素的时候，由于没有可以交换的节点，因此直接返回 head 就可以了。而对于节点超过一个的情况，在处理的时候，就应该将节点两两组合进行处理，也就是说：

function swapPairs(head: ListNode | null): ListNode | null {
  let result = head
  let prev = null
  let currentNode = head
  while(currentNode && currentNode.next) {
    // 如果当前节点为头节点，则应该保存它的下一个节点，因为交换之后，原来的第二个节点变成链表的头节点，
    // 因此需要将这个链表的新的头部作为结果返回。
    if (currentNode === head) {
      result = currentNode.next
    }
    // 将当前节点与后一个节点进行交换
    const nextNode = currentNode.next
    currentNode.next = nextNode.next
    nextNode.next = currentNode
    // 如果记录了前一个节点，则应该将前一个节点的 next 更改为交换后的节点
    if (prev) {
      prev.next = nextNode
    }
    prev = currentNode
    currentNode = currentNode.next
  }
  return result
};

上面的解法中，迭代中的逻辑需要有一个判断当前节点是否为头节点的逻辑，以及判断是否记录了 prev 的逻辑。这里可以使用虚拟头节点来省略判断的逻辑：

function swapPairs(head: ListNode | null): ListNode | null {
  let dummyHead = new ListNode(0, head)
  let prev: ListNode = dummyHead
  let currentNode: ListNode | null = dummyHead.next
  while(currentNode && currentNode.next) {
    // 交换当前这一轮的两个节点位置
    const nextNode = currentNode.next
    currentNode.next = nextNode.next
    nextNode.next = currentNode
    // 更新上一轮最后一个节点的 next 
    prev.next = nextNode
    prev = currentNode
    currentNode = currentNode.next
  }
  return dummyHead.next
}

解法二：递归

function swapPairs(head: ListNode | null): ListNode | null {
  // 链表为空
  // 链表节点数只有一个
  // 链表节点数为奇数
  // 链表节点数为偶数
  if (head === null || head.next === null) {
    return head
  }
  const nextNode = head.next
  head.next = swapPairs(nextNode.next)
  nextNode.next = head
  return nextNode
};