排序链表篇

插入排序

147. 对链表进行插入排序

解题思路

为了简化操作，首先声明虚拟头节点dummy，然后用curr指针扫描整个链表：

在扫描过程中比较curr指针节点和其下一节点的节点值大小，若小于等于则继续步进扫描；
若大于则先缓存此节点，再将其从链表中删除，删除后，从头扫描链表找到合适的位置（第一个大于此节点值的节点的前驱节点）插入此节点。

最后返回dummy.next。

JavaScript

const insertionSortList = head => {
  const dummy = new ListNode(-1, head)
  let [prev, curr] = [null, dummy.next]
  while (curr && curr.next) {  // 扫描链表
    if (curr.val <= curr.next.val) {
      curr = curr.next  // 步进
    } else {
      const next = curr.next  // 缓存节点
      curr.next = next.next  // 从链表中删除
      // 从头扫描找到第一个大于此节点值的节点的前驱节点
      prev = dummy
      while (prev.next.val <= next.val) {
        prev = prev.next
      }
      // 插入节点
      next.next = prev.next
      prev.next = next
    }
  }
  return dummy.next
}

时间复杂度：O(n^2)；空间复杂度：O(1)。

归并排序

148. 排序链表

解题思路

归并归并，首先是归，如何二分链表呢？使用快慢指针法：

初始化快慢指针let [s, f] = [head, head.next]；
快指针走两步，慢指针走一步，当快指针越界时，慢指针恰好到达中点；
从慢指针处切断成两链。

递归版

JavaScript

const merge = (l1, l2) => {
  const dummy = new ListNode(-1)
  let p = dummy
  while (l1 && l2) {
    if (l1.val < l2.val) {
      p.next = l1
      l1 = l1.next
    } else {
      p.next = l2
      l2 = l2.next
    }
    p = p.next
  }
  p.next = l1 ? l1 : l2
  return dummy.next
}

const sortList = head => {
  if (!head || !head.next) return head
  let [s, f] = [head, head.next]
  while (f && f.next) {
    s = s.next
    f = f.next.next
  }
  const r = s.next
  s.next = null
  return merge(sortList(head), sortList(r))
}

时间复杂度：O(nlogn)；空间复杂度：O(logn)。

迭代版

JavaScript

const sortList = head => {
  if (!head || !head.next) return head
  const dummy = new ListNode(-1, head)
  let [len, curr] = [0, head]
  // 获取表长
  while (curr) {
    len++
    curr = curr.next
  }
  for (let subLen = 1; subLen < len; subLen <<= 1) {
    let [prev, curr] = [dummy, dummy.next]
    while (curr) {
      const l1 = curr
      // 对链表进行切割
      for (let i = 1; i < subLen && curr.next; i++) {
        curr = curr.next
      }
      const l2 = curr.next
      curr.next = null  // 切割结束
      curr = l2
      // 再次切割
      for (let i = 1; i < subLen && curr && curr.next; i++) {
        curr = curr.next
      }
      let next = null
      if (curr) {
        next = curr.next
        curr.next = null  // 切割结束
      }
      prev.next = merge(l1, l2)
      while (prev.next) {
        prev = prev.next
      }
      curr = next
    }
  }
  return dummy.next
}

时间复杂度：O(nlogn)；空间复杂度：O(logn)。

奇偶链表

328. 奇偶链表

解题思路

声明odd指针扫描奇数结点，even指针扫描偶数结点，遍历链表：

将奇数节点的.next指针，指向偶数节点的后一个节点；
步进奇数节点；
将偶数节点的.next指针，指向奇数节点的后一个节点；
步进偶数节点。

扫描结束时，奇链偶链分开，此时odd指向奇数节点链的尾节点，连接奇数节点与偶数节点链，返回头节点head。

JavaScript

const oddEvenList = head => {
  if (!head) return head
  let [odd, even, eHead ] = [head, head.next, head.next]
  while (even && even.next) {
    // 将奇数节点的 .next 指针，指向偶数节点的后一个节点
    odd.next = even.next
    // 步进奇数节点
    odd = odd.next
    // 将偶数节点的 .next 指针，指向奇数节点的后一个节点
    even.next = odd.next
    // 步进偶数节点
    even = even.next
  }
  odd.next = eHead
  return head
}

时间复杂度：O(n)；空间复杂度：O(1)。

重排链表

剑指 Offer II 026. 重排链表

解题思路

分三步完成：

寻找链表中点，并从中间切断；
反转后半部分链表；
依次（拉拉链）合并两链表。

JavaScript

const reorderList = head => {
  // 找到链表中点
  if (!head || !head.next) return head
  let [s, f] = [head, head.next]
  while (f && f.next) {
    s = s.next
    f = f.next.next
  }
  // 切断链表
  const r = s.next
  s.next = null
  // 反转链表
  let [prev, curr] = [null, r]
  while (curr) {
    const next = curr.next
    curr.next = prev
    prev = curr
    curr = next
  }
  // 依次合并
  while (head && prev) {
    let l1_rest = head.next
    let l2_rest = prev.next
    // 拉拉链
    head.next = prev
    head = l1_rest
    prev.next = head
    prev = l2_rest
  }
  // return head
}

时间复杂度：O(n)；空间复杂度：O(1)。

回文链表

剑指 Offer II 027. 回文链表

解题思路

分四步完成：

寻找链表中点，并从中间切断；
反转后半部分链表；
依次比较两链表节点值是否相同，若有不同就不是回文链表；
遍历完未发现对应节点不同，将后半部分链表再次反转，然后拼接回原链表。

JavaScript

const isPalindrome = head => {
  if (!head) return true
  // 找到链表中点
  let [s, f] = [head, head.next]
  while (f && f.next) {
    s = s.next
    f = f.next.next
  }
  // 切断链表
  const r = s.next
  s.next = null
  // 反转链表
  const reverse = head => {
    if (!head || !head.next) return head
    let [prev, curr] = [null, head]
    while (curr) {
      const next = curr.next
      curr.next = prev
      prev = curr
      curr = next
    }
    return prev
  }
  const revR = reverse(r)
  // 逐一判断
  let [l1, l2, ret] = [head, revR, true]
  while (l1 && l2) {
    if (l1.val !== l2.val) return false
    l1 = l1.next
    l2 = l2.next
  }
  // 恢复后半部分，并接回
  s.next = reverse(revR)
  return true
}

时间复杂度：O(n)；空间复杂度：O(1)。

排序的循环链表

剑指 Offer II 029. 排序的循环链表

解题思路

由于是循环单调非递减的链表，所以当插入新值时：

若链表为null，直接新建节点，将.next指向自己，返回该节点；
若链表不为null时，设curr = head，在循环链表中查找（curr.next != head）:
- 若curr.val <= val <= curr.next.val，则val应该在[curr, curr.next]插入；
- 若curr.val > curr.next.val，即curr为最大值，curr.next为最小值：
  - 若val >= curr.val，则在最大值curr后插入，即在[curr, curr.next]插入；
  - 若val <= curr.next.val，则在最小值curr.next前插入，即在[curr, curr.next]插入。
- 若遍历完循环链表中的所有节点之后，仍然没有遇到上述三种情况，则循环链表中的所有节点值都相同，因此新节点插入循环链表中的任何位置仍可以使循环链表保持有序，故此时仍可在在[curr, curr.next]之间插入新节点。

JavaScript

const insert = (head, val) => {
  if (!head) {
    const curr = new Node(val)
    curr.next = curr
    return curr
  }
  let curr = head
  // 在循环链表中查找
  while (curr.next != head) {
    if (val >= curr.val && val <= curr.next.val) break
    if (curr.val > curr.next.val) {
      if (val >= curr.val || val <= curr.next.val) break
    }
    curr = curr.next
  }
  curr.next = new Node(val, curr.next)
  return head
}

时间复杂度：O(n)；空间复杂度：O(1)。

排序链表篇 ​

插入排序 ​

归并排序 ​

递归版 ​

迭代版 ​

奇偶链表 ​

重排链表 ​

回文链表 ​

排序的循环链表 ​

排序链表篇

插入排序

归并排序

递归版

迭代版

奇偶链表

重排链表

回文链表

排序的循环链表