143. 重排链表（JS实现）_js单链表排序

1 题目

给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1:
给定链表 1->2->3->4, 重新排列为 1->4->2->3.
示例 2:
给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.

2 思路

这道题的主要思路首先遍历一次链表获取整个链表长度，并将节点存储在数组中，再按题目要求连接链表，注意链表长度的奇偶不同时，最后一个节点的处理不同。题解中还有一种反转后半部分链表的解法。
1、先找处链表L的中间结点，为此设置两个指针p和q，指针p每次走一步，指针q每次走两步，当指针q到达链尾时，指针p正好在链表的中间结点；
2、然后将L的后半段结点原地逆置；
3、从单链表前后两段中 依次各取一个结点，按要求重排；

3代码

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {void} Do not return anything, modify head in-place instead.
 */
var reorderList = function(head) {
  if (!head || !head.next || !head.next.next) return head;
  const arr = [];

  let len = 0;
  while(head) {
    arr[len] = head;
    len++;
    head = head.next;
  }

  let l = Math.floor(len/2);
  for (let i=0; i<l; i++) {
    if (i !== l -1 || len % 2 !== 0) {
      arr[len - i - 1].next = arr[i].next;
      arr[i].next = arr[len-i-1];
    }

    if (i === l - 1) {    //最后一个节点
      if (len % 2 !== 0) {
        arr[len - i - 1].next.next = null;
      } else {
        arr[i].next.next = null;
      }
    }
  }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38