链表

其他

# 啥都不是

# lc206. 反转链表简单hot

题目描述

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

示例 1：

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

1
2

示例 2：

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

1
2

示例 3：

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

1
2

思路：

先声明保存上一个(前驱)结点的变量
把后节点指向他的前节点
把他当做前一个节点准备下一次操作
把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
};

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

时间复杂度O(n)

空间复杂度O(1)

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

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

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

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

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

整体流程图（以 1 → 2 → 3 为例）

初始：reverseList(1)
- 调用 reverseList(2)
  - 调用 reverseList(3)
    - 返回 3（到达 base case）
进入回溯：
- 2.next.next = 2 → 3 → 2
- 2.next = null → 3 → 2 → null
- 然后返回 newHead = 3
再回溯：
- 1.next.next = 1 → 2 → 1
- 1.next = null → 3 → 2 → 1 → 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
};

1
2
3
4
5
6
7
8
9
10

时间复杂度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]

1
2

示例 2：

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

1
2

提供一种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
};

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

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

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

 function reverse(start, end) {
    //       [1,      2, 3, 4]
    //  pre  start         end stop
    let pre = null;
    let stop = end.next;
    while(start !== stop) {
        let next = start.next;
        start.next = pre;

        pre = start;
        start = next;
    }
 }

function reverseKGroup(head: ListNode | null, k: number): ListNode | null {
    //              [1,  2,  3,  4,  5,  6]; k = 4;
    // dummy(pre) start         end next
    let dummy = new ListNode(-1);
    dummy.next = head;
    let pre = dummy;
    while(true) {
        let end = pre;
        for(let i = 0; i < k && end !== null; i++) {
            end = end.next;
        }
        if(!end) break;

        let start = pre.next;
        let next = end.next;

        reverse(start, end);

        pre.next = end;
        start.next = next;
        pre = start;
    }

    return dummy.next;
};

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
39
40
41
42
43
44
45
46
47
48
49
50
51

# 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。

1
2
3
4
5
6
7
8
9
10

示例 2：

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

G = [0, 3, 1, 4]

输出: 2

解释: 

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

1
2
3
4
5
6
7
8
9
10

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

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

/**
 * @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
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

/**
 * @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
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# lc2. 两数相加中等

题目描述

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

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

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

示例 1：

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

输出：[7,0,8]

解释：342 + 465 = 807.

1
2
3
4
5

示例 2：

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

输出：[0]

1
2
3

示例 3：

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

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

1
2
3

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

/**
 * 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
};

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

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

空间复杂度：O(1)

# lc445. 两数相加 II中等

题目描述

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

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

示例1：

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

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

1
2
3

示例2：

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

输出：[8,0,7]

1
2
3

示例3：

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

输出：[0]

1
2
3

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

/**
 * @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
};

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

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

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

# lc61. 旋转链表中等

题目描述

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

示例 1：

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

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

1
2
3

示例 2：

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

输出：[2,0,1]

1
2
3

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

/**
 * @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
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

时间复杂度：O(n)

空间复杂度：O(1)

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

题目描述

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

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

示例 1：

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

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

1
2
3

示例 2：

输入：head = []

输出：[]

1
2
3

示例 3：

输入：head = [1]

输出：[1]

1
2
3

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

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

class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

function swapPairs(head) {
  const dummy = new ListNode(0, head);
  let prev = dummy;

  while (prev.next && prev.next.next) {
    const first = prev.next;
    const second = first.next;

    // 交换两个节点
    first.next = second.next;
    second.next = first;
    prev.next = second;

    // 前进到下一组
    prev = first;
  }

  return dummy.next;
}

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

时间复杂度：O(n)

空间复杂度：O(1)

var swapPairs = function(head) {
  // base case：链表为空或只有一个节点
  if (!head || !head.next) return head;

  let first = head;
  let second = head.next;

  // 递归交换后面的节点
  first.next = swapPairs(second.next);
  second.next = first;

  return second;
};

1
2
3
4
5
6
7
8
9
10
11
12
13

时间复杂度：O(n)

空间复杂度：O(n) 递归的调用栈

# lc86. 分隔链表中等

题目描述

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

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

示例 1：

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

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

1
2
3

示例 2：

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

输出：[1,2]

1
2
3

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

/**
 * @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
};

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

时间复杂度: 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 的字符串表示是 [] 。

1
2
3
4
5
6
7
8
9

示例 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 。前面部分的长度大于等于后面部分的长度。

1
2
3
4
5
6
7

我们可以先计算链表的长度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
};

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

时间复杂度: 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]

1
2
3

示例 2：

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

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

1
2
3

示例 3：

输入：head = []

输出：[]

1
2
3

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

function sortList(head) {
  if (!head || !head.next) return head;

  // 快慢指针找中点
  let slow = head, fast = head.next;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }

  // 分成两半
  const mid = slow.next;
  slow.next = null;

  // 递归排序左右部分
  const left = sortList(head);
  const right = sortList(mid);

  // 合并两个有序链表
  return merge(left, right);
}

function merge(l1, l2) {
  const dummy = new ListNode(0);
  let cur = dummy;

  while (l1 && l2) {
    if (l1.val < l2.val) {
      cur.next = l1;
      l1 = l1.next;
    } else {
      cur.next = l2;
      l2 = l2.next;
    }
    cur = cur.next;
  }

  cur.next = l1 || l2;
  return dummy.next;
}

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
39
40

时间复杂度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]]

1
2
3

示例 2：

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

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

1
2
3

示例 3：

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

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

1
2
3

示例 4：

输入：head = []

输出：[]

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

1
2
3
4
5

第一次循环在每个节点后面插入一个同样的节点，第二次循环给每个新增的节点指向对应的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
};

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

时间复杂度O(n)

空间复杂度O(n)

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

题目描述

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

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

示例 1：

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

1
2
3

示例 2：

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

1
2
3

示例 3：

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

1
2

示例 4：

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

1
2

示例 5：

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

1
2

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

1
2
3
4

上次更新: 2025/05/28, 09:28:27

← 双指针