啥都不是

lc206. 反转链表简单hot

题目描述

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

法一： 迭代

思路：

• 先声明保存上一个(前驱)结点的变量

• 把后节点指向他的前节点

• 把他当做前一个节点准备下一次操作

• 把cur移到他的后节点准备下一次操作

来个图展示一下

/**
 * 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 {ListNode}
 */
var reverseList = function(head) {
    if(!head || !head.next) return head
    let pre = null
    let cur = head
    let next = null
    while(cur) {
        // 先把下一个(后)节点保存起来,防止丢失了
        next = cur.next
        // 把后节点指向他的前节点
        cur.next = pre

        // 把他当做前一个节点准备下一次操作
        pre = cur
        // 把cur移到他的后节点准备下一次操作
        cur = next
    }

    head = pre
    return head
};

时间复杂度O(n)

空间复杂度O(1)

法二: 递归

利用递归依次反转当前head 后继next

在这里正好复习一下如何才能做好递归

1. 首先对于节点1来说，他只需要除了他后面的所有节点翻转即可 即reverseList关注的是翻转 -> 返回头结点

1. 递归之后出现以下情形 上图可以写成这样 var reverseHead = reverseList(next)
2. 接下来就是翻转节点1后面的节点 head.next.next=head

1. 接着把head的下一个节点设为null 即head.next = null 最后返回头结点

var reverseList = function(head) {
	if(!head || !head.next) return head    
    var next = head.next
    // 递归反转
    var reverseHead = reverseList(next)
    // 变换指针
    next.next = head
    head.next = null
    return reverseHead
};

时间复杂度O(n)

空间复杂度O(n)

lc92. 进阶：反转链表 II中等hot

题目描述

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

示例 1：

输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]

示例 2：

输入：head = [5], left = 1, right = 1
输出：[5]

思路：

提供一种leetcode官方的穿针引线(头插法)

整体思想是：在需要反转的区间里，每遍历到一个节点，让这个新节点来到反转部分的起始位置。下面的图展示了整个流程。

下面我们具体解释如何实现。使用三个指针变量 pre、curr、next 来记录反转的过程中需要的变量，它们的意义如下：

curr：指向待反转区域的第一个节点 left；next：永远指向 curr 的下一个节点，循环过程中，curr 变化以后 next 会变化；pre：永远指向待反转区域的第一个节点 left 的前一个节点，在循环过程中不变。第 1 步，我们使用 ①、②、③ 标注「穿针引线」的步骤。

操作步骤：

先将 curr 的下一个节点记录为 next；执行操作 ①：把 curr 的下一个节点指向 next 的下一个节点；执行操作 ②：把 next 的下一个节点指向 pre 的下一个节点；执行操作 ③：把 pre 的下一个节点指向 next。第 1 步完成以后「拉直」的效果如下：

第 2 步，同理。同样需要注意 「穿针引线」操作的先后顺序。

第 2 步完成以后「拉直」的效果如下：

第 3 步，同理。

第 3 步完成以后「拉直」的效果如下：

实现了一次循环完成翻转

时间复杂度O(n)

空间复杂度O(1)

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} left
 * @param {number} right
 * @return {ListNode}
 */
var reverseBetween = function(head, left, right) {
    const dummyNode = new ListNode(-1)
    dummyNode.next = head
    let pre = dummyNode
    for(let i = 0; i < left - 1; i++) {
        pre = pre.next        
    }

    let cur = pre.next
    for(let j = 0; j < right - left; j++) {
        const next = cur.next
        cur.next = next.next
        next.next = pre.next
        pre.next = next
    }
    return dummyNode.next
};

lc25:k个一组反转链表中等hot

/*
 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */

/**
  * 
  * @param head ListNode类 
  * @param k int整型 
  * @return ListNode类
  */
function reverseKGroup(head, k) {
    //局部翻转 pre指向头，尾指向next
    let preHead = new ListNode(-1);
    preHead.next = head;
    let pre = preHead
    while(head){
        //每一轮为一组 尾结点移动
        let tail = pre;
        for(let i =0;i<k;i++){
            //如果凑不够k个，结束
            tail = tail.next;
             if(!tail) return preHead.next;
        }
        let next = tail.next;
        //翻转 head 到 tail，返回翻转后的头尾
        [head,tail]= reverse(head,tail)
        //拼接
        pre.next = head;
        tail.next = next;
        //更新
        pre = tail;
        head = tail.next;
    }
    return preHead.next
}

function reverse(head,tail){
    //局部翻转列表：遍历head~tail的节点，每个节点指向前一个结点
    let pre = null;
    let current = head;
    while(pre!==tail){
        [current.next,pre,current]=[pre,current,current.next]
        
    }
    
    return [tail,head];
}

lc817. 链表组件中等

题目描述

给定链表头结点 head，该链表上的每个结点都有一个 唯一的整型值 。

同时给定列表 G，该列表是上述链表中整型值的一个子集。

返回列表 G 中组件的个数，这里对组件的定义为：链表中一段最长连续结点的值（该值必须在列表 G 中）构成的集合。

示例 1：

输入: 
head: 0->1->2->3

G = [0, 1, 3]

输出: 2

解释: 

链表中,0 和 1 是相连接的，且 G 中不包含 2，所以 [0, 1] 是 G 的一个组件，同理 [3] 也是一个组件，故返回 2。

示例 2：

输入: 
head: 0->1->2->3->4

G = [0, 3, 1, 4]

输出: 2

解释: 

链表中，0 和 1 是相连接的，3 和 4 是相连接的，所以 [0, 1] 和 [3, 4] 是两个组件，故返回 2。

思路

就是这nums数组是这个链表的子集，那么要解出nums里面有几个组件，就是说当nums中出现了他没有的val，那就断开，算两个分开的组件，那么我们采用索引法来解决

这里暂且定义名为isComponent，如果当前G中有这个值，并且isComponent是false，就说明这是一个新的组件，结果加一，如果G中不存在这个值，直接将isComponent置为false，将指针向后移动一位，继续遍历。只要当前指针存在，就一直遍历，直到遍历完整个链表

先用indexOf进行索引

/**
 * @param {ListNode} head
 * @param {number[]} nums
 * @return {number}
 */
var numComponents = function(head, nums) {
  let isComponent = false
  let res = 0
  while(head) {
    if(nums.indexOf(head.val) > -1) {
      if(!isComponent) {
        isComponent = true
        res++
      }
    } else {
      isComponent = false
    }
    head = head.next
  }
  return res
};

用set进行优化索引

/**
 * @param {ListNode} head
 * @param {number[]} nums
 * @return {number}
 */
var numComponents = function(head, nums) {
  let isComponent = false
  let res = 0
  let set = new Set(nums)
  while(head) {
    if(set.has(head.val)) {
      if(!isComponent) {
        isComponent = true
        res++
      }
    } else {
      isComponent = false
    }
    head = head.next
  }
  return res
};

lc2. 两数相加中等

题目描述

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0之外，这两个数都不会以 0 开头。

示例 1：

输入：l1 = [2,4,3], l2 = [5,6,4]

输出：[7,0,8]

解释：342 + 465 = 807.

示例 2：

输入：l1 = [0], l2 = [0]

输出：[0]

示例 3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]

输出：[8,9,9,9,0,0,0,1]

思路

就是另外创建一个链表 注意进位

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
  let l3 = new ListNode(null)
  let curry = 0
  let p1 = l1, p2 = l2, p3 = l3
  while(p1 || p2 || curry) {
    const v1 = p1 ? p1.val : 0
    const v2 = p2 ? p2.val : 0
    const val = v1 + v2 + curry
    curry = Math.floor(val / 10)
    p3.next = new ListNode(val % 10)
    if(p1) p1 = p1.next
    if(p2) p2 = p2.next
    p3 = p3.next
  }
  // if(curry) p3.next = new ListNode(curry)

  return l3.next
};

时间复杂度：O(max(m, n))

空间复杂度：O(1)

lc445. 两数相加 II中等

题目描述

给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

你可以假设除了数字 0 之外，这两个数字都不会以零开头。

示例1：

输入：l1 = [7,2,4,3], l2 = [5,6,4]

输出：[7,8,0,7]

示例2：

输入：l1 = [2,4,3], l2 = [5,6,4]

输出：[8,0,7]

示例3：

输入：l1 = [0], l2 = [0]

输出：[0]

思路

用两个栈遍历两个链表 然后推进去，后进先出来解决

/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
  const stack1 = [], stack2 = []
  let curry = 0
  let l3 = new ListNode(null)
  let p1 = l1, p2 = l2, p3 = l3
  while(l1 || l2) {
    stack1.push(p1)
    stack2.push(p2)
    if(p1) p1 = p1.next
    if(p2) p2 = p2.next
  }
  while(stack1.length || stack2.length || curry) {
    let n1 = stack1.pop()
    let n2 = stack2.pop()
    const v1 = n1 ? n1.val : 0
    const v2 = n2 ? n2.val : 0
    const sum = v1 + v2 + curry
    curry = Math.floor(sum / 10)
    const temp = new ListNode(sum % 10)
    temp.next = p3
    p3 = temp
  }
  return p3
};

时间复杂度：O(max(m, n))

空间复杂度：O(m + n)

lc61. 旋转链表中等

题目描述

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置

示例 1：

输入：head = [1,2,3,4,5], k = 2

输出：[4,5,1,2,3]

示例 2：

输入：head = [0,1,2], k = 4

输出：[2,0,1]

思路

就是把链表变成环形链表，然后根据旋转次数裁断他

/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var rotateRight = function(head, k) {
  let tail = head
  let length = 1
  if(!head || !head.next) return head
  while(tail && tail.next) {
    tail = tail.next
    length++
  }
  tail.next = head

  k = k % length
  for(let i = 0; i < length - k; i++) {
    tail = tail.next
  }
  head = tail.next
  tail.next = null
  return head
};

时间复杂度：O(n)

空间复杂度：O(1)

lc24. 两两交换链表中的节点中等

题目描述

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1：

输入：head = [1,2,3,4]

输出：[2,1,4,3]

示例 2：

输入：head = []

输出：[]

示例 3：

输入：head = [1]

输出：[1]

思路

借助翻转链表的思路进行两两反转

因为反转链表，所以至少需要三个临时变量

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function(head) {
  let dummyHead = new ListNode(null)
  dummyHead.next = head
  let pre = dummyHead
  while(pre.next && pre.next.next) {
    const cur = pre.next
    const next = cur.next

    cur.next = next.next    
    next.next = pre.next
    pre.next = next

    pre = cur
  }
  return dummyHead.next
};

时间复杂度：O(n)

空间复杂度：O(1)

lc86. 分隔链表中等

题目描述

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于x 的节点之前。

你应当 保留 两个分区中每个节点的初始相对位置。

示例 1：

输入：head = [1,4,3,2,5,2], x = 3

输出：[1,2,2,4,3,5]

示例 2：

输入：head = [2,1], x = 2

输出：[1,2]

思路

就是就是创建两个链表，然后小的连到小的链表，大的连到大的链表上，然后把两个链表连在一起

/**
 * @param {ListNode} head
 * @param {number} x
 * @return {ListNode}
 */
var partition = function(head, x) {
  let smallHead = new ListNode(null)
  let largeHead = new ListNode(null)
  let p1 = smallHead, p2 = largeHead

  while(head) {
    if(head.val < x) {
      p1.next = head
      p1 = p1.next
    } else {
      p2.next = head
      p2 = p2.next
    }
    head = head.next
  }

  p1.next = largeHead.next
  p2.next = null

  return smallHead.next
};

时间复杂度: O(n)

空间复杂度: O(n)

lc725. 分隔链表 II中等

题目描述

给你一个头结点为 head 的单链表和一个整数 k ，请你设计一个算法将链表分隔为 k 个连续的部分。

每部分的长度应该尽可能的相等：任意两部分的长度差距不能超过 1 。这可能会导致有些部分为 null 。

这 k 个部分应该按照在链表中出现的顺序排列，并且排在前面的部分的长度应该大于或等于排在后面的长度。

返回一个由上述 k 部分组成的数组。

示例 1：

输入：head = [1,2,3], k = 5

输出：[[1],[2],[3],[],[]]

解释：

第一个元素 output[0] 为 output[0].val = 1 ，output[0].next = null 。

最后一个元素 output[4] 为 null ，但它作为 ListNode 的字符串表示是 [] 。

示例 2：

输入：head = [1,2,3,4,5,6,7,8,9,10], k = 3

输出：[[1,2,3,4],[5,6,7],[8,9,10]]

解释：

输入被分成了几个连续的部分，并且每部分的长度相差不超过 1 。前面部分的长度大于等于后面部分的长度。

思路

我们可以先计算链表的长度length，尽可能均分链表。然后再计算每个子链表的长度：先计算平均每个子链表的长度为length/k，倘若不能整除，剩余的length%k个元素，则前length%k个子链表的长度再加一

/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode[]}
 */
var splitListToParts = function(head, k) {
    let cur = head
    let length = 0
    while(cur){
        cur = cur.next
        length++
    }

    // 每一项的长度
    let width = Math.floor(length / k), curry = length % k
    let num, temp
    
    let res = new Array(k);
    for(let i = 0; i < k; i++) {
        // 计算从剩余链表中截取的长度
        num = i < curry ? width + 1 : width
        // 从剩余链表中截取num个元素
        temp = cur = head;
        for(let j = 1; cur && j < num; j++) {
            cur = cur.next;
        }
        // 修改head指向
        if(cur) {
            head = cur.next;
            cur.next = null;
        } else {
            head = null;
        }
        res[i] = temp;
    }
    return res
};

时间复杂度: O(N + k)，N 指的是链表的结点数，若 k 很大，则还需要添加许多空列表。

空间复杂度: O(max(N, k))，存放答案所需的空间。

lc148. 排序链表中等hot

题目描述

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

进阶：

你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

例 1：

输入：head = [4,2,1,3]

输出：[1,2,3,4]

示例 2：

输入：head = [-1,5,3,4,0]

输出：[-1,0,3,4,5]

示例 3：

输入：head = []

输出：[]

思路

他要求是时间复杂度为nlogn，那就是提示我们使用归并排序

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var sortList = function(head) {
  if(!head || !head.next) return head

  let slow = fast = head
  while(fast.next && fast.next.next) {
    fast = fast.next.next
    slow = slow.next
  }
  const middle = slow.next
  slow.next = null

  const left = head
  const right = middle
  return merge(sortList(left), sortList(right))
};

var merge = function(left, right) {
  const res = new ListNode(null)
  let cur = res
  while(left && right) {
    if(left.val < right.val) {
      cur.next = left
      left = left.next
    } else {
      cur.next = right
      right = right.next
    }
    cur = cur.next
  }
  cur.next = left ? left : right

  return res.next
}

时间复杂度O(nlogn)

空间复杂度O(1)

lc138. 复制带随机指针的链表中等

题目描述

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如，如果原链表中有 X 和 Y两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点x 和 y ，同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

val：一个表示 Node.val 的整数。

random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。

你的代码 只 接受原链表的头节点 head 作为传入参数。

示例 1：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]

输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2：

输入：head = [[1,1],[2,1]]

输出：[[1,1],[2,1]]

示例 3：

输入：head = [[3,null],[3,0],[3,null]]

输出：[[3,null],[3,0],[3,null]]

示例 4：

输入：head = []

输出：[]

解释：给定的链表为空（空指针），因此返回 null。

思路

第一次循环在每个节点后面插入一个同样的节点，第二次循环给每个新增的节点指向对应的random节点，然后断开链表

/**
 * @param {Node} head
 * @return {Node}
 */
var copyRandomList = function(head) {
  if(!head) return null
  let cur = head
  // 在每个节点后面新增一个同样的节点
  while(cur) {
    let p = new Node(cur.val)
    p.next = cur.next
    cur.next = p
    cur = p.next
  }
  // 指向random节点
  cur = head
  while(cur) {
    if(cur.random) {
     cur.next.random = cur.random.next
    }
    cur = cur.next.next
  }
  // 断开节点
  let dummyNode = new Node(null)
  dummyNode.next = head
  let p = dummyNode
  cur = head
  while(cur) {
    p.next = cur.next
    p = p.next
    cur.next = p.next
    cur = cur.next
  }
  return dummyNode.next
};

时间复杂度O(n)

空间复杂度O(n)

lc237. 删除链表中的节点简单

题目描述

请编写一个函数，用于 删除单链表中某个特定节点 。在设计函数时需要注意，你无法访问链表的头节点 head ，只能直接访问 要被删除的节点 。

题目数据保证需要删除的节点 不是末尾节点 。

示例 1：

输入：head = [4,5,1,9], node = 5
输出：[4,1,9]
解释：指定链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9

示例 2：

输入：head = [4,5,1,9], node = 1
输出：[4,5,9]
解释：指定链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9

示例 3：

输入：head = [1,2,3,4], node = 3
输出：[1,2,4]

示例 4：

输入：head = [0,1], node = 0
输出：[1]

示例 5：

输入：head = [-3,5,-99], node = -3
输出：[5,-99]

var deleteNode = function(node) {
  node.val = node.next.val
  node.next = node.next.next
};