Skip to main content

两两交换链表中的节点

题目​

给定一个链表, 两两交换其中相邻的节点, 并返回交换后的链表. 你不能只是单纯的改变节点内部的值, 而是需要实际的进行节点交换.

提示:
  • 链表中节点的数目在范围 [0, 100] 内
  • 0 <= Node.val <= 100
示例
输入: [1, 2, 3, 4, 5]

输出: [2, 1, 4, 3, 5]
输入: [1]

输出: [1]
输入: []

输出: []

题解​

  1. 创建一个 dummy 链表, 将它的 next 指向 head
  2. curr 表示当前到达的节点, 初始时 curr = dummy, 每次需要交换 curr 后面的两个节点
  3. 如果下一个节点为 null, 意味着到头了; 抑或如果下下个节点为 null, 意味链表长度为奇数, 没法再做交换, 结束循环
  4. 交换之前的节点关系是 curr -> node1 -> node2, 交换之后的节点关系要变成 curr -> node2 -> node1
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function (head) {
  const dummy = new ListNode(null)
  dummy.next = head
  let curr = dummy

  while (curr.next !== null && curr.next.next !== null) {
    const first = curr.next
    const second = curr.next.next

    // 把 second 的下一个放到 first 的下一个
    first.next = second.next

    // second 的下一个指向 first
    second.next = first

    // 把 second 放到 curr.next 下
    curr.next = second

    // first 赋值给 curr, 实际上就是将 curr 往后走了两步
    curr = first
  }

  return dummy.next
}