链表

1.合并两个有序链表

https://leetcode-cn.com/problems/merge-two-sorted-lists/
递归

迭代

var mergeTwoLists = function(l1, l2) {
    const a =  new ListNode(0)
    let preNode = a
    while (l1 && l2) {
        if (l1.val < l2.val) {
            preNode.next = l1
            l1 = l1.next
        } else {
            preNode.next = l2
            l2 = l2.next
        }
        preNode = preNode.next
    }
    preNode.next = l1 ? l1 : l2
    return a.next
}

2、删除排序链表中的重复元素

3、合并k个排序链表

分治法

var mergeKLists = function (lists) {
  /* 分而治之 */
  if (lists.length <= 1) return lists[0] || null;
  const newLists = [];
  for (let i = 0; i < lists.length; i += 2) {
    newLists.push(merge(lists[i], lists[i + 1]));
  }
  return mergeKLists(newLists);
};

4、判断链表是否有环

https://leetcode-cn.com/problems/linked-list-cycle/solution/huan-xing-lian-biao-kuai-man-zhi-zhen-by-zf1b/

5、环形链表2 返回入环点的索引 done

var detectCycle = function(head) {
    let fast = head
    let slow = head
    let flag = 0
     while(fast && fast.next) {
        fast = fast.next.next
        slow = slow.next
        if (slow == fast) {
            flag = 1
            break
        }
    }
    if (flag == 0) return null
  //注意，将fast移动到head部位，再次循环
    fast = head
    while (fast && slow) {
        if (fast == slow) {
            return fast
        }
        fast = fast.next
        slow = slow.next     
    }
};

5、反转链表

var reverseList = function(head) {
    let node = head
    let preNode = null
    let temp = null
    while (node) {
      //注意
        temp = node.next
        node.next = preNode
        preNode = node
        node = temp
    }
    return preNode
};