LeetCode题解：143. 重排链表，数组，JavaScript，详细注释

[chencl1986]

原题链接：143. 重排链表

解题思路：

1. 将链表的每个元素都放入数组list。
2. 使用左指针i和右指针j向中间推进直到相遇。
3. 将i和j所指元素依次存入新数组newList中。
4. 遍历newList，生成新链表并返回。

/**
 * @param {ListNode} head
 * @return {void} Do not return anything, modify head in-place instead.
 */
var reorderList = function (head) {
  let list = []; // 使用数组存储链表
  let node = head; // 使用node遍历链表

  // 遍历链表，将每个元素依次存入数组
  while (node) {
    list.push(node);
    node = node.next;
  }

  let newList = []; // 使用新数组，存储新排序的链表节点
  let i = 0; // 使用i指针从头往后遍历list
  let j = list.length - 1; // 使用j指针从后往前遍历list

  // 左右指针不断向中间移动，知道相遇
  while (i <= j) {
    // 将i、j指向的元素，依次存入newList
    newList.push(list[i++], list[j--]);
  }

  let newNode = newList[0]; // 缓存新链表的头节点

  // newList的每个元素，就是新链表的每个节点
  for (let i = 1; i < newList.length; i++) {
    // 将每个节点连接到链表
    newNode.next = newList[i];
    // 将新链表节点向后移动一位，待连接下一个节点
    newNode = newNode.next;
  }
  // 将尾节点的next置为null，避免链表出现环
  newNode.next = null;

  // head也是新链表的头结点
  return head;
};

5. 由于我们只关心新链表节点的指向关系，因此可以不用newList存储新链表，直接修改list中各个节点的指向即可。

/**
 * @param {ListNode} head
 * @return {void} Do not return anything, modify head in-place instead.
 */
var reorderList = function (head) {
  let list = []; // 使用数组存储链表
  let node = head; // 使用node遍历链表

  // 遍历链表，将每个元素依次存入数组
  while (node) {
    list.push(node);
    node = node.next;
  }

  let i = 0; // 使用i指针从头往后遍历list
  let j = list.length - 1; // 使用j指针从后往前遍历list

  // 两个指针向中间推进，直到相遇
  while (i < j) {
    // 将i指向j，并将i向后移动一位
    list[i++].next = list[j];
    // 将j指向i，并将j向前移动一位
    list[j--].next = list[i];
  }
  // list[i].next需要设置为null，否则链表会成环
  list[i].next = null;

  // head也是新链表的头结点
  return head;
};