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

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

Category	Difficulty	Likes	Dislikes
algorithms	Medium (71.02%)	1474	-

Tags
Companies
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

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

提示：

• 链表中节点的数目在范围 [0, 100] 内
• 0 <= Node.val <= 100

---

Discussion | Solution

思路

创建一个哑结点，处理最前两个翻转后队首指针的问题，后续使用 prev 以及 temp，原地交换链表顺序，最后返回 dummy 节点的 next 即可。

解答

/*
 * @lc app=leetcode.cn id=24 lang=javascript
 *
 * [24] 两两交换链表中的节点
 */

// @lc code=start
/**
 * Definition for singly-linked list.
function ListNode(val, next) {
    this.val = (val===undefined ? 0 : val)
     this.next = (next===undefined ? null : next)
}
 */

function ListNode(val, next) {
  this.val = val === undefined ? 0 : val;
  this.next = next === undefined ? null : next;
}

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function (head) {
  let dummy = new ListNode();
  dummy.next = head;
  let p = dummy.next,
    prev = dummy,
    temp;

  while (p && p.next) {
    // 记录原下一个节点
    temp = p.next;
    // 将当前next设为原下一个节点的next
    p.next = p.next.next;
    // 原下一个节点的next设为当前节点
    temp.next = p;
    // 原上一个节点的next设为原下一个节点
    prev.next = temp;
    // 更新 prev 为当前节点
    prev = p;
    // 继续处理接下来的节点
    p = p.next;
  }

  return dummy.next;
};
// @lc code=end