链表专题

反转链表

给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。

数据范围： 0≤n≤1000

要求：空间复杂度 O(1) ，时间复杂度O(n) 。

如当输入链表{1,2,3}时，

经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。

以上转换过程如下图所示：

• 示例1

输入：

{1,2,3}

返回值：

{3,2,1}

• 示例2

输入：

{}

返回值：

{}

说明：

空链表则输出空               

双指针迭代法

在遍历链表时，将当前节点的next 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。

function ReverseList( head ) {
    let prev = null;
    let curr =head;
    while(curr != null) {
      let temp = curr.next;
      curr.next = prev;
      prev = curr;
      curr = temp;
    }
    // 最后要返回prev
    return prev;
}

递归

// 解法二： 递归
function ReverseList2( head ) {
  if(head == null || head.next == null) {
    return head
  }
  // 保存当前的下一个节点
  let nextNode = head.next;
  // 递归调用
  // 从当前节点的下一个结点开始递归调用
  let ans = ReverseList2(nextNode);
  //让当前结点的下一个结点的 next 指针指向当前节点
  nextNode.next = head;
  //同时让当前结点的 next 指针指向NULL ，从而实现从链表尾部开始的局部反转
  head.next = null;
  return ans;
} 

利用栈

先进栈再出栈，由于简单就不写

链表内指定区间反转

将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度O(n)，空间复杂度 O(1)。 例如： 给出的链表为 1→2→3→4→5→NULL, m=2,n=4, 返回 1→4→3→2→5→NULL.

数据范围： 链表长度 0<<size≤1000，0<m≤n≤size，链表中每个节点的值满足 ∣val∣≤1000

要求：时间复杂度 O*(n) ，空间复杂度O*(n)

进阶：时间复杂度 O(n)，空间复杂度 O(1)

输入：

{1,2,3,4,5},2,4

返回值：

{1,4,3,2,5}

输入：

{5},1,1

返回值：

{5}

迭代法

// 解法和上一题类似，不过要做特殊判断，如果从第一个开始逆转，那么就和上一道题类似

function reverseBetween( head ,  m ,  n ) {
  let prev = null; // prev指向要逆转的链表区间的第一个结点
  let curr = head;
  let newHead = head;
  let ReversePrevNode = null; // prev的前一个结点
  for(let i = 1; i <= m; i++) {
    ReversePrevNode = prev
    prev = curr;
    curr = curr.next;
  }
  let ReverseLastNode = prev; // 指向要逆转的链表区间的第一个结点,逆转后会变成逆转区间的最后一个结点
  for(let i = 1; i <= n - m; i++) {
    let temp = curr.next;
    curr.next = prev;
    prev = curr;
    curr = temp;
  }
  if(ReversePrevNode != null) {
    ReversePrevNode.next = prev;
    
  }
  if(ReverseLastNode != null) {
    ReverseLastNode.next = curr;
  }
  if(m >= 2) {
    return newHead;
  } else {
    return prev;
  }
}

利用栈

利用栈来解决只是翻转链表区间那里和上面的解法不一样，其他类似，总体来说增加了空间复杂度，所以总的来说不推荐这种做法

// 解法二： 利用栈
function reverseBetween2( head ,  m ,  n ) {
  let stack = []
  let newHead = head;
  let node = head;
  let prev = null;
  for(let i = 1; i < m; i++) {
    prev = node;
    node = node.next;
  }
  // prev现在已经是逆转的前一个结点了
  let ReverseLastNode = null;
  for(let i = m; i <= n; i++) {
    stack.push(node);
    node = node.next;
    ReverseLastNode = node;
  }
  let p = null;
  if(stack.length > 0) {
    p = stack.pop();
  }
  let ReverseNewHead = p;
  while(stack.length > 0) {
    let node = stack.pop()
    p.next = node;
    p = p.next;
  }
  if(p != null) {
    p.next = ReverseLastNode;
  }
  if(prev != null) { // 说明不是是从第一个结点开始逆转的
    prev.next = ReverseNewHead
  }
  if(m == 1) { 
    return ReverseNewHead
  } else {
    return newHead
  }
}

链表中的节点每k个一组翻转

将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表 如果链表中的节点数不是 k 的倍数，将最后剩下的节点保持原样 你不能更改节点中的值，只能更改节点本身。

数据范围： 0≤n≤2000 ，1≤k≤2000 ，链表中每个元素都满足 0≤≤val≤1000 要求空间复杂度 O(1)，时间复杂度O(n)

例如：

给定的链表是 1→2→3→4→51→2→3→4→5

对于 k=2 , 你应该返回 2→1→4→3→5

对于 k=3 , 你应该返回 3→2→1→4→5

输入：

{1,2,3,4,5},2

返回值：

{2,1,4,3,5}

输入：

{},1

返回值：

{}

function reverseKGroup(head, k) {
   // 找到每次翻转的尾部
  let tail = head;
  // 遍历k次到尾部
  for(let i = 0; i < k; i++) {
    // 如果不足k到了链表尾，直接返回，不翻转
    if(tail == null) {
      return head;
    }
    tail = tail.next;
  }
  // 翻转时需要的前序和当前节点
  let prev = null;
  let curr = head;
  while(curr != tail) {
    let temp = curr.next;
    curr.next = prev;
    prev = curr;
    curr = temp;
  }
  // 当前尾指向下一段要翻转的链表
  head.next = reverseKGroup(tail, k);
  return prev;
}

合并两个排序的链表

输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。

数据范围： 0≤n≤1000，−1000≤节点值≤1000 要求：空间复杂度 O(1)，时间复杂度 O(n)

如输入{1,3,5},{2,4,6}时，合并后的链表为{1,2,3,4,5,6}，所以对应的输出为{1,2,3,4,5,6}，转换过程如下图所示：

或输入{-1,2,4},{1,3,4}时，合并后的链表为{-1,1,2,3,4,4}，所以对应的输出为{-1,1,2,3,4,4}，转换过程如下图所示：

输入：

{1,3,5},{2,4,6}

返回值：

{1,2,3,4,5,6}

输入：

{},{}

返回值：

{}

复制

输入：

{-1,2,4},{1,3,4}

返回值：

{-1,1,2,3,4,4}

迭代

function Merge( pHead1 ,  pHead2 ) {
  if(pHead1 == null) return pHead2;
  if(pHead2 == null) return pHead1;
  let newHead = null;
  let p = null;
  let p1 = pHead1, p2 = pHead2;
  while(p1!= null && p2 != null) {
    if(p1.val < p2.val) {
      if(newHead == null) {
        newHead = p1;
        p = newHead;
      } else {
        p.next = p1;
        p = p.next;
      }
      p1 = p1.next;
    } else {
      if(newHead == null) {
        newHead = p2;
        p = newHead;
      } else {
        p.next = p2;
        p = p.next;
      }
      p2 = p2.next;
    }
  }
  if(p1 != null) {
    p.next = p1;
  }
  if(p2 != null) {
    p.next = p2;
  }
  return newHead;
}

递归

function Merge2( pHead1 ,  pHead2 ) {
  if(pHead1 == null || pHead2 == null) {
    return pHead1 == null ? pHead2 : pHead1;
  }
  if(pHead1.val < pHead2.val) {
    pHead1.next = Merge2(pHead1.next, pHead2)
    return pHead1;
  } else {
    pHead2.next = Merge2(pHead1, pHead2.next);
    return pHead2;
  }
}

最后一种方法，借助辅助空间

先把所有的值放在一个数组里面，然后排序，最后再重新构造一个链表

合并k个已排序的链表

合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。

数据范围：节点总数 0≤n≤5000，每个节点的val满足∣val∣<=1000

要求：时间复杂度O(nlogn)

输入：

[{1,2,3},{4,5,6,7}]

返回值：

{1,2,3,4,5,6,7}

输入：

[{1,2},{1,4,5},{6}]

返回值：

{1,1,2,4,5,6}

两两合并

借助上一题的思路，两两先合并，然后再和后一个合并

// 思路：两两合并
function mergeKLists( lists ) {
  const length = lists.length;
  
  if(length == 1) return lists[0];
  for(let i = 0; i < length - 1; i++) {
    lists[i + 1] = merge(lists[i], lists[i+1]);
  }
  return lists[length - 1];
}
function merge(head1, head2) {
  if(head1 == null) return head2;
  if(head2 == null) return head1;
  if(head1.val < head2.val) {
    head1.next = merge(head1.next, head2);
    return head1;
  } else {
    head2.next = merge(head1, head2.next);
    return head2;
  }
}

归并排序

和上述思想差不多

function merge(head1, head2) {
  if(head1 == null) return head2;
  if(head2 == null) return head1;
  if(head1.val < head2.val) {
    head1.next = merge(head1.next, head2);
    return head1;
  } else {
    head2.next = merge(head1, head2.next);
    return head2;
  }
}
// 归并排序
// divideMerge
function divideMerge(lists, left , right) {
  if(left > right) {
    return null
  } else if (left == right) {
    return lists[left];
  }
  let mid = parseInt((left + right) / 2);
  return merge(divideMerge(lists, left, mid), divideMerge(lists, mid + 1, right));
}
function mergeKLists( lists ) {
  return divideMerge(lists, 0 , lists.length - 1);
}

优先队列

知识点：优先队列

优先队列即PriorityQueue，是一种内置的机遇堆排序的容器，分为大顶堆与小顶堆，大顶堆的堆顶为最大元素，其余更小的元素在堆下方，小顶堆与其刚好相反。且因为容器内部的次序基于堆排序，因此每次插入元素时间复杂度都是O(log2n)，而每次取出堆顶元素都是直接取出。

思路：

如果非要按照归并排序的合并思路，双指针不够用，我们可以直接准备k个指针，每次比较得出k个数字中的最小值。为了快速比较k个数字得到最小值，我们可以利用Java提供的PriorityQueue或者C++SLT提供的优先队列或者Python提供的PriorityQueue可以实现，它是一种参照堆排序的容器，容器中的元素是有序的，如果是小顶堆，顶部元素就是最小的，每次可以直接取出最小的元素。也就是说

每次该容器中有k个元素，我们可以直接拿出最小的元素，再插入下一个元素，相当于每次都是链表的k个指针在比较大小，只移动最小元素的指针。

具体做法：

• step 1：不管是Java还是C++都需要重载比较方法，构造一个比较链表节点大小的小顶堆。（Python版本直接加入节点值）
• step 2：先遍历k个链表头，将不是空节点的节点加入优先队列。
• step 3：每次依次弹出优先队列中的最小元素，将其连接在合并后的链表后面，然后将这个节点在原本链表中的后一个节点（如果不为空的话）加入队列，类似上述归并排序双指针的过程。

javascript 之优先队列 (opens new window)

有错误，暂时没找出来

// 先实现一个优先队列
class PriorityQueue {
  constructor(compare) {
    if(typeof compare !== 'function') {
      throw new Error('compare function required!')
    }
    this.data = []
    this.compare = compare
  }
  // 二分查找，寻找插入位置
  search(target) {
    let low = 0, high = this.data.length;
    while(low < high) {
      let mid = low + (high - low) >> 1
      if(this.compare(this.data[mid].val, target.val) > 0) {
        high = mid;
      } else {
        low = mid + 1;
      }
    }
    return low;
  }
  // 添加
  push(elem) {
    let index = this.search(elem);
    this.data.splice(index, 0, elem);
    return this.data.length;
  }
  // 取出最优元素
  pop() {
    return this.data.pop();
  }
  // 查看最优元素
  peek() {
    return this.data[this.data.length - 1];
  }
  isEmpty() {
    return this.data.length == 0
  }
}
function mergeKLists( lists ) {
  // 小顶堆
  const queue = new PriorityQueue((a, b) => b.val - a.val);
  // 遍历所有链表的第一个元素
  for(let i = 0; i < lists.length; i++) {
    // 不为空则加入小顶堆
    if(lists[i] != null) {
      queue.push(lists[i]);
    }
  }
  // 表头
  let newHead = new ListNode(-1);
  let curr = newHead;
  while(!queue.isEmpty()) {
    // 取出最小的元素
    let temp = queue.pop();
    curr.next = temp;
    curr = curr.next;
    // 每次取出链表的后一个元素加入小顶堆
    if(temp.next != null) {
      queue.push(temp.next);
    }
  }
  // 去掉表头
  return newHead.next;
}

判断链表中是否有环

判断给定的链表中是否有环。如果有环则返回true，否则返回false。

数据范围：链表长度 0≤n≤10000，链表中任意节点的值满足 ∣val∣<=100000

要求：空间复杂度 O(1)，时间复杂度 O(n)

输入分为两部分，第一部分为链表，第二部分代表是否有环，然后将组成的head头结点传入到函数里面。-1代表无环，其它的数字代表有环，这些参数解释仅仅是为了方便读者自测调试。实际在编程时读入的是链表的头节点。

例如输入{3,2,0,-4},1时，对应的链表结构如下图所示：

可以看出环的入口结点为从头结点开始的第1个结点（注：头结点为第0个结点），所以输出true。

输入：

{3,2,0,-4},1

返回值：

true

说明：

第一部分{3,2,0,-4}代表一个链表，第二部分的1表示，-4到位置1（注：头结点为位置0），即-4->2存在一个链接，组成传入的head为一个带环的链表，返回true           

输入：

{1},-1

返回值：

false

说明：

第一部分{1}代表一个链表，-1代表无环，组成传入head为一个无环的单链表，返回false           

输入：

{-1,-7,7,-4,19,6,-9,-5,-2,-5},6

返回值：

true

快慢指针

function hasCycle( head ) {
  let slow = head;
  let fast = head;
  while(fast!= null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
    if(slow == fast) {
      return true;
    }
  }
  return false;
}

第二种方法

用一个数组存储一下访问过的指针，如果指针存在就说明存在链表

链表中环的入口结点

给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。

数据范围： n≤10000，1<=结点值<=10000

要求：空间复杂度 O(1)，时间复杂度 O(n)

例如，输入{1,2},{3,4,5}时，对应的环形链表如下图所示：

可以看到环的入口结点的结点值为3，所以返回结点值为3的结点。

输入描述：

输入分为2段，第一段是入环前的链表部分，第二段是链表环的部分，后台会根据第二段是否为空将这两段组装成一个无环或者有环单链表

返回链表的环的入口结点即可，我们后台程序会打印这个结点对应的结点值；若没有，则返回对应编程语言的空结点即可。

输入：

{1,2},{3,4,5}

返回值：

3

说明：

返回环形链表入口结点，我们后台程序会打印该环形链表入口结点对应的结点值，即3   

输入：

{1},{}

返回值：

"null"

说明：

没有环，返回对应编程语言的空结点，后台程序会打印"null"   

输入：

{},{2}

返回值：

2

说明：

环的部分只有一个结点，所以返回该环形链表入口结点，后台程序打印该结点对应的结点值，即2   

快慢指针

function EntryNodeOfLoop(pHead)
{
    let slow = pHead;
    let fast = pHead;
    while(fast != null && fast.next != null) {
      slow = slow.next;
      fast = fast.next.next;
      if(slow == fast) {
        let index1 = pHead;
        let index2 = slow;
        while(index1 != index2) {
          index1 = index1.next;
          index2 = index2.next;
        }
        return index1;
      }
    }
    return null;
}

借助辅助数组

// 利用数组保存访问过的结点
function EntryNodeOfLoop(pHead) {
  let arr = []
  let p = pHead;
  while(p != null) {
    if(arr.includes(p)) {
      return p;
    }
    arr.push(p);
    p = p.next;
  }
  return null;
}

链表中倒数最后k个结点

输入一个长度为 n 的链表，设链表中的元素的值为 ai ，返回该链表中倒数第k个节点。

如果该链表长度小于k，请返回一个长度为 0 的链表。

数据范围：0≤n≤105，0≤ai≤109，0≤k≤109

要求：空间复杂度 O(n)，时间复杂度 O(n)

进阶：空间复杂度 O(1)，时间复杂度 O(n)

例如输入{1,2,3,4,5},2时，对应的链表结构如下图所示：

其中蓝色部分为该链表的最后2个结点，所以返回倒数第2个结点（也即结点值为4的结点）即可，系统会打印后面所有的节点来比较。

输入：

{1,2,3,4,5},2

返回值：

{4,5}

说明：

返回倒数第2个节点4，系统会打印后面所有的节点来比较。 

输入：

{2},8

返回值：

{}

快慢指针

function FindKthToTail( pHead ,  k ) {
  let slow = pHead;
  let fast = pHead;
  let i = 0;
  while(fast && i < k) {
    fast = fast.next;
    i++;
  }
  if(i != k) {
    return null;
  }
  while(fast) {
    slow = slow.next;
    fast = fast.next;
  }
  return slow;
}

借助栈

function FindKthToTail( pHead ,  k ) {
  let stack = []
  let p = pHead;
  if(pHead == null || k == 0) {
    return null;
  }
  while(p) {
    stack.push(p);
    p = p.next;
  }
  if(stack.length < k) { // 说明不存在最后k个结点
    return null;
  }
  let firstNode = stack.pop();
  for(let i = 0; i < k -1; i++) {
    let temp = stack.pop();
    temp.next = firstNode;
    firstNode = temp;
  }
  return firstNode;
}

删除链表的倒数第n个节点

给定一个链表，删除链表的倒数第 n 个节点并返回链表的头指针 例如，

给出的链表为: 1→2→3→4→5,n*=2. 删除了链表的倒数第 n*个节点之后,链表变为1→2→3→5.

数据范围： 链表长度 0≤n≤1000，链表中任意节点的值满足 0≤val≤100

要求：空间复杂度 O(1)，时间复杂度 O(n) 备注：

题目保证 n 一定是有效的

输入：

{1,2},2    

返回值：

{2} 

双指针

function removeNthFromEnd( head ,  n ) {
  let slow = head;
  let fast = head;
  // 由于题中说了保证n一定是有效地，所以就采用for循环
  // 如果不保证n有效，就要采用while循环，并且最后判断n==i
  for(let i = 0; i < n; i++) {
    fast = fast.next;
  }
  let prev = head;
  let falg = false; // 判断是不是要删除第一个结点
  // 在这一步，其实也可以判断如果fast为空就直接返回head.next
  while(fast) {
    falg = true;
    prev = slow;
    slow = slow.next;
    fast = fast.next;
  }
  prev.next = slow.next;
  if(!falg) {
    // 说明是要删除第一个结点
    return slow.next;
  } else {
    return head;
  }
}

时间复杂度O(N), 空间复杂度O(1)

计算链表长度

首先从头节点开始对链表进行一次遍历，得到链表的长度 L。随后再从头节点开始对链表进行一次遍历，当遍历到第 L-n+1 个节点时，它就是我们需要删除的节点 为了方便删除操作，可以从哑节点开始遍历 L-n+1 个节点。当遍历到第 L-n+1 个节点时，它的下一个节点就是需要删除的节点，这样只需要修改一次指针，就能完成删除操作

// 方法二： 计算链表长度
function removeNthFromEnd( head ,  n ) {
  let prev = head;
  let q = head;
  let length = 0;
  while(q) {
    length++;
    q = q.next;
  }
  // length - n + 1个结点就是我们要删除的节点
  if(length == n) { // 说明要删除第一个结点
    return head.next;
  }
  // let i = 0;
  // while(prev) {
  //   i++;
  //   if(i == length - n) {
  //     prev.next = prev.next.next;
  //   }
  //   prev = prev.next;
  // }
  // 记得是从1开始的
  for(let i = 1; i < length - n; i++) {
    prev = prev.next;
  }
  if(prev.next == null) { // 说明要删除的是最后一个结点
    prev == prev.next;
  } else {
    prev.next = prev.next.next;
  }
  return head;
}

两个链表的第一个公共结点

输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

数据范围： n≤1000 要求：空间复杂度 O(1)，时间复杂度 O(n)

例如，输入{1,2,3},{4,5},{6,7}时，两个无环的单向链表的结构如下图所示：

可以看到它们的第一个公共结点的结点值为6，所以返回结点值为6的结点。

输入描述：

输入分为是3段，第一段是第一个链表的非公共部分，第二段是第二个链表的非公共部分，第三段是第一个链表和第二个链表的公共部分。 后台会将这3个参数组装为两个链表，并将这两个链表对应的头节点传入到函数FindFirstCommonNode里面，用户得到的输入只有pHead1和pHead2。

返回值描述：

返回传入的pHead1和pHead2的第一个公共结点，后台会打印以该节点为头节点的链表。

输入：

{1,2,3},{4,5},{6,7}

复制

返回值：

{6,7}

说明：

第一个参数{1,2,3}代表是第一个链表非公共部分，第二个参数{4,5}代表是第二个链表非公共部分，最后的{6,7}表示的是2个链表的公共部分
这3个参数最后在后台会组装成为2个两个无环的单链表，且是有公共节点的          

输入：

{1},{2,3},{}

返回值：

{}

说明：

2个链表没有公共节点 ,返回null，后台打印{}     

双指针

function FindFirstCommonNode(pHead1, pHead2)
{
  let p = pHead1;
  let q = pHead2;
  while(p != q) {
    p == null ? p = pHead2 : p = p.next;
    q == null ? q = pHead1 : q = q.next;
  }
  return p; // 最后如果不存在公共结点都会等于null然后退出while循环
}

链表相加(二)

假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。

给定两个这种链表，请生成代表两个整数相加值的结果链表。

数据范围：0≤n*,m≤1000000，链表任意值 0≤val≤9 要求：空间复杂度 O(n)，时间复杂度 O(n)

例如：链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0。

输入：

[9,3,7],[6,3]

返回值：

{1,0,0,0}

说明：

如题面解释     

输入：

[0],[6,3]

返回值：

{6,3}

先逆序相加再逆序

function addInList( head1 ,  head2 ) {
  // write code here
  // 先将链表逆置
  let p = reverseList(head1);
  let q = reverseList(head2);
  // 添加一个头结点
  let newHead = new ListNode(-1);
  let h = newHead;
  let prefix = 0;
  while(p!= null || q!= null) {
    let num = prefix + (p != null ? p.val: 0) + (q != null ? q.val : 0);
    if(num >= 10) {
      prefix = parseInt(num / 10);
      num = num % 10;
    } else {
      prefix = 0
    }
    let temp = new ListNode(num);
    h.next = temp;
    h = temp;
    if( p != null) {
      p = p.next;
    }
    if(q != null) {
      q = q.next;
    }
  }
  if(prefix != 0) {
    h.next = new ListNode(prefix);
  }
  return reverseList(newHead.next);
}
function reverseList(head) {
  let prev = null;
  let curr = head;
  while(curr) {
    let temp = curr.next;
    curr.next = prev;
    prev = curr;
    curr = temp;
  }
  return prev
}

借助栈

与上述不同的是，反转链表的过程由栈来完成

// 借助栈
function addInList( head1 ,  head2 ) {
  if(head1 == null) {
    return head2;
  }
  if(head2 == null) {
    return head1;
  }
  let stack1 = []
  let stack2 = []
  let p = head1;
  let q = head2;
  while(p) {
    stack1.push(p.val);
    p = p.next;
  }
  while(q) {
    stack2.push(q.val);
    q = q.next;
  }
  let prefix = 0;

  let stack = []
  while(stack1.length > 0 || stack2.length > 0) {
    let num1 = stack1.length > 0 ? stack1.pop() : 0;
    let num2 = stack2.length > 0 ? stack2.pop() : 0;
    let num = num1 + num2 + prefix;
    if(num >= 10) {
      prefix = parseInt(num / 10);
      num = num % 10;
    } else {
      prefix = 0
    }
    stack.push(num);
  }
  if(prefix != 0) {
    stack.push(prefix);
  }
  let newHead = new ListNode(-1);
  let h = newHead;
  while(stack.length > 0) {
    let temp = new ListNode(stack.pop());
    h.next = temp;
    h = temp; 
  }
  return newHead.next;
}

单链表的排序

给定一个节点数为n的无序单链表，对其按升序排序。

数据范围：0<n≤100000，保证节点权值在[−109,109]之内。

要求：空间复杂度O(n)，时间复杂度O(nlogn)

输入：

[1,3,2,4,5]

返回值：

{1,2,3,4,5}

输入：

[-1,0,-2]

返回值：

{-2,-1,0}

辅助数组+排序

function sortInList(head) {
    let queue = [];
    let p = head;
    while (p) {
        queue.push(p.val);
        p = p.next;
    }
    // 从大到小排序
    queue.sort((a, b) => b - a);
    let newHead = new ListNode(-1);
    let q = newHead;
    while (queue.length > 0) {
        let temp = new ListNode(queue.pop());
        q.next = temp;
        q = temp;
    }
    return newHead.next;
}

归并排序

可以把链表从中间拆开，然后利用归并排序

function mergeList(head1, head2) {
  if(head1 == null)
    return head2;
  if(head2 == null)
    return head1;
  let p = head1, q = head2, newHead = new ListNode(-1), curr = newHead;
  while(p && q) {
    if(p.val < q.val) {
      curr.next = p;
      curr = p;
      p = p.next;
    } else {
      curr.next = q;
      curr = q;
      q = q.next;
    }
  }
  if(p) {
    curr.next = p;
  }
  if (q) {
    curr.next = q;
  }
  return newHead.next;
}
function sortInList(head) {
  if(head == null || head.next == null) {
    return head;
  }
  let left = head;
  let mid = head.next;
  let right = head.next.next;
  // 右边的指针到达末尾时，中间的指针指向该段链表的中间
  while(right != null && right.next != null) {
    left = left.next;
    mid = mid.next;
    right = right.next.next;
  }
   //左边指针指向左段的左右一个节点，从这里断开
   left.next = null;
   return mergeList(sortInList(head), sortInList(mid));
}

判断一个链表是否为回文结构

给定一个链表，请判断该链表是否为回文结构。

回文是指该字符串正序逆序完全一致。

数据范围： 链表节点数 0≤n≤105，链表中每个节点的值满足 ∣val∣≤107

输入：

{1}

返回值：

true

输入：

{2,1}

返回值：

false

说明：

2->1     

输入：

{1,2,2,1}

返回值：

true

说明：

1->2->2->1     

借助数组

借助数组，转为普通的回文问题

// 将链表用数组存储起来
function isPail( head ) {
  let p = head;
  let arr = [];
  while(p) {
    arr.push(p.val);
    p = p.next;
  }
  for(let i = 0; i < parseInt(arr.length / 2); i++) {
    if(arr[i] != arr[arr.length - i - 1]){
      return false;
    }
  }
  return true;
}

双指针

// 后半部分逆转和前半部分比较

// 双指针
function isPail( head ) {
  let p = head;
  let q = head;
  while(q != null && q.next != null) {
    p = p.next;
    q = q.next.next;
  }
  // 如果q不为空，说明链表的长度是奇数个
  if (q != null) {
      p = p.next;
  }
  // 反转的是链表后半部分
  p = reverseList(p);
  q = head;
  while(p) {
    if(p.val != q.val) {
      return false;
    }
    p = p.next;
    q = q.next;
  }
  return true;
}
function reverseList(head) {
  let prev = null;
  let curr = head;
  while(curr) {
    let temp = curr.next;
    curr.next = prev;
    prev = curr;
    curr = temp;
  }
  return prev;
}

链表的奇偶重排

给定一个单链表，请设定一个函数，将链表的奇数位节点和偶数位节点分别放在一起，重排后输出。

注意是节点的编号而非节点的数值。

数据范围：节点数量满足 0≤n≤105，节点中的值都满足 0≤val≤1000

要求：空间复杂度 O(n)，时间复杂度 O(n)

输入：

{1,2,3,4,5,6}

返回值：

{1,3,5,2,4,6}

说明：

1->2->3->4->5->6->NULL
重排后为1->3->5->2->4->6->NULL
   

输入：

{1,4,6,3,7}

返回值：

{1,6,7,4,3}

说明：

1->4->6->3->7->NULL
重排后为
1->6->7->4->3->NULL
奇数位节点有1,6,7，偶数位节点有4,3。重排后为1,6,7,4,3

function oddEvenList( head ) {
  if(head == null) return head;
  let odd = head; // 奇
  let even = head.next; // 偶
  let newEvenHead = even;
  while(even && even.next) {
    // 偶元素指向奇元素的下一个（偶元素）
    odd.next = even.next;
    // odd进入后一个奇数位
    odd = odd.next;
    // even连接后一个奇数的后一位，即偶数位
    even.next = odd.next;
    // even进入后一个偶数位
    even = even.next;
  }
  // even整体接在odd后面
  odd.next = newEvenHead;
  return head;
}

删除有序链表中重复的元素-I

删除给出链表中的重复元素（链表中元素从小到大有序），使链表中的所有元素都只出现一次 例如： 给出的链表为1→1→2,返回1→2 给出的链表为1→1→2→3→3,返回1→2→3.

数据范围：链表长度满足 0≤n≤100，链表中任意节点的值满足 ∣val∣≤100

进阶：空间复杂度O(1)，时间复杂度O(n)

输入：

{1,1,2}

复制

返回值：

{1,2}

复制

输入：

{}

返回值：

{}

function deleteDuplicates( head ) {
  if(head == null)
    return head;
  let prev = head;
  let curr = head.next;
  while(curr) {
    while(curr && prev.val == curr.val) {
      curr = curr.next;
    }
    if(curr) {
      // 找到下一个不同个的元素
      prev.next = curr;
      prev = prev.next;
      curr = curr.next;
    } else {
      // 解决全是重复元素
      prev.next = null;
    }
  }
  return head;
}

删除有序链表中重复的元素-II

给出一个升序排序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。 例如： 给出的链表为1→2→3→3→4→4→5, 返回1→2→5. 给出的链表为1→1→1→2→3, 返回2→3.

数据范围：链表长度 0≤n≤10000，链表中的值满足 ∣val∣≤1000

要求：空间复杂度 O(n)，时间复杂度 O(n)

进阶：空间复杂度O(1)，时间复杂度 O(n)

输入：

{1,2,2}

返回值：

{1}

输入：

{}

返回值：

{}

二分查找/排序

二分查找-I

请实现无重复数字的升序数组的二分查找

给定一个 元素升序的、无重复数字的整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标（下标从 0 开始），否则返回 -1

数据范围：0≤len(nums)≤2×105 ， 数组中任意值满足 ∣val∣≤109

进阶：时间复杂度 O(logn) ，空间复杂度 O(1)

输入：

[-1,0,3,4,6,10,13,14],13

返回值：

6

说明：

13 出现在nums中并且下标为 6     

输入：

[],3

返回值：

-1

说明：

nums为空，返回-1     

输入：

[-1,0,3,4,6,10,13,14],2

返回值：

-1

说明：

2 不存在nums中因此返回 -1     

二维数组中的查找

在一个二维数组array中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

[

[1,2,8,9], [2,4,9,12], [4,7,10,13], [6,8,11,15]

]

给定 target = 7，返回 true。

给定 target = 3，返回 false。

数据范围：矩阵的长宽满足 0≤n,m≤500 ， 矩阵中的值满足 0≤val≤109 进阶：空间复杂度 O(1) ，时间复杂度 O(n+m)

输入：

7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]

返回值：

true

说明：

存在7，返回true   

输入：

1,[[2]]

返回值：

false

输入：

3,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]

返回值：

false

说明：

不存在3，返回false 

// 第一种思路，O（m*n），两层for循环

// 第二种思路，逐行进行二分查找，O(n * logm)

// 第三种思路，O（m + n）

1. 由于行列递增，可以得出： a.在一列中的某个数字，其上的数字都比它小 b.在一行中的某个数字，其右的数字都比它大
2. 搜索流程： a.首先从数组左下角搜索. b.如果当前数字大于target,那么查找往上移一位,如果当前数字小于target,那么查找往右移一位。 c.查找到target,返回true; 如果越界，返回false;

// 从下往上线性搜索
function Find( target ,  array ) {
  let m = array.length;
  let n = array[0].length;
  let right = 0, up = m - 1; // 向右和向上走
  while(right < n && up >= 0) {
    let temp = array[up][right];
    if(temp == target) {
      return true;
    } else if (temp < target) {
      right++;
    } else {
      up--;
    }
  }
  return false;
} 

寻找峰值

给定一个长度为n的数组nums，请你找到峰值并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个所在位置即可。

1.峰值元素是指其值严格大于左右相邻值的元素。严格大于即不能有等于

2.假设 nums[-1] = nums[n] = −∞

3.对于所有有效的 i 都有 nums[i] != nums[i + 1]

4.你可以使用O(logN)的时间复杂度实现此问题吗？

数据范围：

1≤nums.length≤2×105

−231<=nums[i]<=231−1

如输入[2,4,1,2,7,8,4]时，会形成两个山峰，一个是索引为1，峰值为4的山峰，另一个是索引为5，峰值为8的山峰，如下图所示：

输入：

[2,4,1,2,7,8,4]

返回值：

1

说明：

4和8都是峰值元素，返回4的索引1或者8的索引5都可以     

输入：

[1,2,3,1]

返回值：

2

说明：

3 是峰值元素，返回其索引 2     

线性查找

function findPeakElement(nums) {
  if(nums.length == 1) return 0;
  // 这种考虑不到第一个和最后一个
  for(let i = 1; i < nums.length - 1; i++) {
    if(nums[i - 1] < nums[i] && nums[i] > nums[i + 1]) {
      return i;
    }
  }
  // 对第一个和最后一个进行单独考虑
  if(nums[0] > nums[1]) {
    return 0;
  }
  if(nums[nums.length - 1] > nums[nums.length - 1 -1]) {
    return nums.length - 1;
  }
  return -1;
}

二分查找

因为题目将数组边界看成最小值，而我们只需要找到其中一个波峰，因此只要不断地往高处走，一定会有波峰。那我们可以每次找一个标杆元素，将数组分成两个区间，每次就较高的一边走，因此也可以用分治来解决，而标杆元素可以选择区间中点。

//右边是往下，不一定有坡峰
if(nums[mid] > nums[mid + 1])
    right = mid;
//右边是往上，一定能找到波峰
else
    left = mid + 1;

• step 1：二分查找首先从数组首尾开始，每次取中间值，直到首尾相遇。
• step 2：如果中间值的元素大于它右边的元素，说明往右是向下，我们不一定会遇到波峰，但是那就往左收缩区间。
• step 3：如果中间值大于右边的元素，说明此时往右是向上，向上一定能有波峰，那我们往右收缩区间。
• step 4：最后区间收尾相遇的点一定就是波峰。

function findPeakElement( nums ) {
  let left = 0, right = nums.length - 1;
  while(left < right) {
    let mid  = (left + right) >> 1;
    if(nums[mid] > nums[mid + 1]) { // 右边是下降趋势，说明往右边不一定存在峰值
      right = mid;
    } else {
      left = mid + 1; // 右边是上升趋势,一定存在峰值
    }
  }
  return right;
}

数组中的逆序对

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P mod 1000000007 数据范围： 对于 50%的数据, size≤104 对于 100%的数据, size≤105

数组中所有数字的值满0≤val≤109

要求：空间复杂度O(n)，时间复杂度O(nlogn)

输入描述：

题目保证输入的数组中没有的相同的数字

输入：

[1,2,3,4,5,6,7,0]

返回值：

7

输入：

[1,2,3]

返回值：

0

双层循环

// 测试不通过，时间复杂度过高
function InversePairs( nums ) {
  let num = 0;
  for(let i = 0; i < nums.length; i++) {
    for(j = i + 1; j < nums.length; j++) {
      if(nums[j] < nums[i]) {
        num++;
      }
    }
  }
  return num % 1000000007;
}

归并排序

// 利用归并排序
function InversePairs( nums ) {
  let num = 0;
  if(nums.length < 2) return 0;
  mergeSort(nums, 0, nums.length - 1);
  return num;
  function mergeSort(array, left, right) {
    let mid = left + right >> 1;
    if(left < right) {
      // 左子数组
      mergeSort(array, left, mid);
      // 右子数组
      mergeSort(array, mid + 1, right);
      // 合并
      merge(array, left, mid, right);
    }
  }
  function merge(array, left, mid, right) {
    let arr = Array(right - left + 1);
    let p = 0, l = left, r = mid + 1;
    while(l <= mid && r <= right) {
      if(array[l] < array[r]) {
        arr[p] = array[l];
        p++;
        l++;
      } else {
        arr[p] = array[r];
        // 说明存在逆序对
        num += (mid - l + 1);
        num %= 1000000007;
        p++;
        r++;
      }
    }
    while(l <= mid) {
      arr[p++] = array[l++];
    }
    while(r <= right) {
      arr[p++] = array[r++];
    }
    p = 0;
    for(let i = left; i <= right; i++) {
      array[i] = arr[p++];
    }
  }
}

旋转数组的最小数字

有一个长度为 n 的非降序数组，比如[1,2,3,4,5]，将它进行旋转，即把一个数组最开始的若干个元素搬到数组的末尾，变成一个旋转数组，比如变成了[3,4,5,1,2]，或者[4,5,1,2,3]这样的。请问，给定这样一个旋转数组，求数组中的最小值。

数据范围：1≤n≤10000，数组中任意元素的值: 0≤val≤10000

要求：空间复杂度：O(1) ，时间复杂度：O*(*logn)

输入：

[3,4,5,1,2]

返回值：

1

输入：

[3,100,200,3]

返回值：

3

二分法

1、初始化： 声明 i, j 双指针分别指向 array 数组左右两端

2、循环二分： 设 m = (i + j) / 2 为每次二分的中点（ "/" 代表向下取整除法，因此恒有 i≤m1、当 array[m] > array[j] 时： m 一定在 左排序数组 中，即旋转点 x 一定在 [m + 1, j] 闭区间内，因此执行 i = m + 1 2、当 array[m] < array[j] 时： m 一定在 右排序数组 中，即旋转点 x 一定在[i, m]闭区间内，因此执行 j = m 3、当 array[m] = array[j] 时： 无法判断 mm 在哪个排序数组中，即无法判断旋转点 x 在 [i, m] 还是 [m + 1, j] 区间中。解决方案： 执行 j = j - 1 缩小判断范围 3、返回值： 当 i = j 时跳出二分循环，并返回 旋转点的值 array[i] 即可

function minNumberInRotateArray( nums ) {
  // write code here
  let left = 0, right = nums.length - 1;
  while(left < right) {
    // 中间点m
    let mid = left + right >> 1;
     // mid在左排序数组中，旋转点在 [m+1, right] 中
    if(nums[mid] > nums[right]) { // 说明最小值在右边
      left = mid + 1;
    } else if(nums[mid] < nums[right]){
      // mid在右排序数组中，旋转点在[left, mid]中
      right = mid; 
    } else {
      right--;
    }
  }
  return left;
}

比较版本号

牛客项目发布项目版本时会有版本号，比如1.02.11，2.14.4等等

现在给你2个版本号version1和version2，请你比较他们的大小

版本号是由修订号组成，修订号与修订号之间由一个"."连接。1个修订号可能有多位数字组成，修订号可能包含前导0，且是合法的。例如，1.02.11，0.1，0.2都是合法的版本号

每个版本号至少包含1个修订号。

修订号从左到右编号，下标从0开始，最左边的修订号下标为0，下一个修订号下标为1，以此类推。

比较规则：

一. 比较版本号时，请按从左到右的顺序依次比较它们的修订号。比较修订号时，只需比较忽略任何前导零后的整数值。比如"0.1"和"0.01"的版本号是相等的

二. 如果版本号没有指定某个下标处的修订号，则该修订号视为0。例如，"1.1"的版本号小于"1.1.1"。因为"1.1"的版本号相当于"1.1.0"，第3位修订号的下标为0，小于1

三. version1 > version2 返回1，如果 version1 < version2 返回-1，不然返回0.

数据范围：

1<=version1.length,version2.length<=1000

version1 和 version2 的修订号不会超过int的表达范围，即不超过 32 位整数 的范围

进阶： 空间复杂度 O(1) ， 时间复杂度O(n)

输入：

"1.1","2.1"

返回值：

-1

说明：

version1 中下标为 0 的修订号是 "1"，version2 中下标为 0 的修订号是 "2" 。1 < 2，所以 version1 < version2，返回-1
          

输入：

"1.1","1.01"

返回值：

0

说明：

version2忽略前导0，为"1.1"，和version相同，返回0         

输入：

"1.1","1.1.1"

返回值：

-1

说明：

"1.1"的版本号小于"1.1.1"。因为"1.1"的版本号相当于"1.1.0"，第3位修订号的下标为0，小于1，所以version1 < version2，返回-1          

输入：

"2.0.1","2"

返回值：

1

说明：

version1的下标2>version2的下标2，返回1          

输入：

"0.226","0.36"

返回值：

1

说明：

226>36，version1的下标2>version2的下标2，返回1