<EricWXY/>
链表相关题目总结 (js/ts 实现)
ericwxy
  2022-04-05 21:47:38   2024-02-28 13:02:23

链表和树是面试中出现频率较高的数据结构,今天就来总结一波链表相关的常见题目。

两数相加

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

思路

模拟小学数学加法

代码

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
function addTwoNumbers(
  l1: ListNode | null,
  l2: ListNode | null
): ListNode | null {
  const dummy = new ListNode(0);
  let p1 = l1;
  let p2 = l2;
  let p3 = dummy;
  let carry = 0;
  while (p1 || p2) {
    const v1 = p1 ? p1.val : 0;
    const v2 = p2 ? p2.val : 0;

    // 计算和
    const val = v1 + v2 + carry;

    // 进位
    carry = Math.floor(val / 10);
    p3.next = new ListNode(val % 10);

    // 链表next
    if (p1) p1 = p1.next;
    if (p2) p2 = p2.next;
    p3 = p3.next;
  }
  if (carry) p3.next = new ListNode(carry);
  return dummy.next;
}

两数相加 II

给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。

思路

先反转链表，再如法炮制上一题

代码

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
function addTwoNumbers(
  l1: ListNode | null,
  l2: ListNode | null
): ListNode | null {
  const dummy = new ListNode(0);
  let p1 = reverseList(l1);
  let p2 = reverseList(l2);
  let p3 = dummy;
  let carry = 0;
  while (p1 || p2) {
    const v1 = p1 ? p1.val : 0;
    const v2 = p2 ? p2.val : 0;

    // 计算和
    const val = v1 + v2 + carry;

    // 进位
    carry = Math.floor(val / 10);
    p3.next = new ListNode(val % 10);

    // 链表next
    if (p1) p1 = p1.next;
    if (p2) p2 = p2.next;
    p3 = p3.next;
  }
  if (carry) p3.next = new ListNode(carry);
  return reverseList(dummy.next);
}

/**
 * 反转链表（递归实现）
 **/
function reverseList(head: ListNode | null): ListNode | null {
  if (head == null || head.next == null) return head;
  const next = head.next;
  const reverse = reverseList(head.next);
  next.next = head;
  head.next = null;
  return reverse;
}

进阶

本题进阶要求：如果输入链表不能翻转如何解决

在不影响原链表的情况下我们可以引入栈来解决这个问题

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
function addTwoNumbers(
  l1: ListNode | null,
  l2: ListNode | null
): ListNode | null {
  const dummy = new ListNode(0);
  const stack1 = [l1];
  const stack2 = [l2];
  const stack3 = [];

  let p1 = l1;
  let p2 = l2;
  let p3 = dummy;
  let carry = 0;

  while (p1) {
    p1 = p1.next;
    !!p1 && stack1.push(p1);
  }
  while (p2) {
    p2 = p2.next;
    !!p2 && stack2.push(p2);
  }

  p1 = stack1.pop();
  p2 = stack2.pop();

  while (p1 || p2) {
    const v1 = p1 ? p1.val : 0;
    const v2 = p2 ? p2.val : 0;

    // 计算和
    const val = v1 + v2 + carry;

    // 进位
    carry = Math.floor(val / 10);
    stack3.push(new ListNode(val % 10));

    p1 = stack1.pop();
    p2 = stack2.pop();
  }
  !!carry && stack3.push(new ListNode(carry));

  while (stack3.length) {
    p3.next = stack3.pop();
    p3 = p3.next;
  }
  return dummy.next;
}

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

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

方法 1：暴力求解（判断 n 次 next 后是否为 null）

这是我凭直觉想的方法，直接遍历链表在每一次遍历的时候都要去判断 n 个 next 之后是否为 null, 如果为 null 说明这是需要删除的节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
  const dummy = new ListNode(0, head);
  let current = dummy;
  while (!!current) {
    let _next = current;
    for (let i = 0; i <= n; i++) {
      _next = _next?.next;
    }
    // 这里必须为全等(因为迭代后面会出现 undefined)
    if (_next === null) {
      current.next = current.next.next;
    }
    current = current?.next;
  }
  return dummy.next;
}

我们可以看到这种方法遍历每一个节点都要走一个次数为 n 的循环,时间复杂度会激增。固我们需要更优解。

方法 2：求链表长度。

我们可以先求出链表长度,通过 for 循环找到链表长度减去 n 的节点并删除它。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
  const dummy = new ListNode(0, head);
  const len = getListLen(head);
  let current = dummy;
  for (let i = 1; i < len - n + 1; i++) {
    current = current.next;
  }
  current.next = current.next.next;
  return dummy.next;
}

function getListLen(head: ListNode | null): number {
  let length = 0;
  while (!!head) {
    ++length;
    head = head.next;
  }
  return length;
}

方法 3：栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
  const dummy = new ListNode(0, head);
  const stack: ListNode[] = [];
  let current = dummy;
  while (!!current) {
    stack.push(current);
    current = current.next;
  }
  for (let i = 0; i < n; ++i) {
    stack.pop();
  }
  const prev = stack.pop();
  prev.next = prev.next.next;
  return dummy.next;
}

方法 4：快慢指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
  let fast = head;
  let slow = head;
  for (let i = 0; i < n; i++) {
    fast = fast.next;
  }
  if (!fast) return head.next;
  while (!!fast.next) {
    fast = fast.next;
    slow = slow.next;
  }
  slow.next = slow.next.next;
  return head;
}

方法 5：递归

1
2
3
4
5
6
7
8
9
10
11
12
function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
  const remove = (node: ListNode | null, n: number) => {
    if (!node) return 0;
    const pos = remove(node.next, n) + 1;
    if (pos === n + 1) node.next = node.next.next;
    return pos;
  };

  const pos = remove(head, n);
  if (pos === n) return head.next;
  return head;
}

反转链表

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

方法 1：直接遍历

这种方法应该属于比较优秀的方法了，没有借助任何别的数据结构单纯运用的是链表的操作。

1
2
3
4
5
6
7
8
9
10
11
function reverseList(head: ListNode | null): ListNode | null {
  let prev = null;
  let current = head;
  while (!!current) {
    let nextTemp = current.next;
    current.next = prev;
    prev = current;
    current = nextTemp;
  }
  return prev;
}

方法 2：栈

看到倒叙我们很直接的就可以联想到栈。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function reverseList(head: ListNode | null): ListNode | null {
  if (head == null) return null;
  const stack = [head];
  let current = head;
  while (!!current) {
    current = current.next;
    !!current && stack.push(current);
  }
  const result = stack[stack.length - 1];
  current = stack.pop();
  while (!!stack.length && !!current) {
    const next = stack.pop();
    current.next = next;
    current = current.next;
  }
  head.next = null;
  return result;
}

方法 3：递归

既然我们可以运用栈，那是不是可以利用 callStack 来试试。

1
2
3
4
5
6
7
8
function reverseList(head: ListNode | null): ListNode | null {
  if (head == null || head.next == null) return head;
  const next = head.next;
  const reverse = reverseList(head.next);
  next.next = head;
  head.next = null;
  return reverse;
}

从尾到头打印链表

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

方法 1：利用链表遍历 + 数组 api

1
2
3
4
5
6
7
8
9
10
11
12
function reversePrint(head: ListNode | null): number[] {
  let current: ListNode | null = head;
  const result: number[] = [];

  while (!!current) {
    result.unshift(current.val);
    current = current.next;
  }

  // 或者利用数组的 push 推入配合 return  result.reverse()
  return result;
}

方法 2：反转链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function reversePrint(head: ListNode | null): number[] {
  let current = reverseList(head);
  const result: number[] = [];

  while (!!current) {
    result.push(current.val);
    current = current.next;
  }
  return result;
}

function reverseList(head: ListNode | null): ListNode | null {
  let prev = null;
  let current = head;
  while (!!current) {
    let nextTemp = current.next;
    current.next = prev;
    prev = current;
    current = nextTemp;
  }
  return prev;
}

方法 3：利用栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function reversePrint(head: ListNode | null): number[] {
  const stack = [];
  const result = [];

  let current = head;
  while (!!current) {
    stack.push(current.val);
    current = current.next;
  }

  while (!!stack.length) {
    result.push(stack.pop());
  }
  return result;
}

方法 4：递归

1
2
3
4
5
6
7
8
9
10
11
function reversePrint(head: ListNode | null): number[] {
  const result: number[] = [];
  const pushItem = (node: ListNode | null) => {
    if (node != null) {
      if (node.next != null) pushItem(node.next);
      result.push(node.val);
    }
  };
  pushItem(head);
  return result;
}

合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

方法 1：迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function mergeTwoLists(
  list1: ListNode | null,
  list2: ListNode | null
): ListNode | null {
  const dummp = new ListNode(0);
  let p = dummp;
  let p1 = list1;
  let p2 = list2;

  const insertNext = (_q: ListNode) => {
    p.next = _q;
    return _q.next;
  };

  while (p1 && p2) {
    if (p1.val < p2.val) p1 = insertNext(p1);
    else p2 = insertNext(p2);
    p = p.next;
  }
  if (p1) p.next = p1;
  if (p2) p.next = p2;
  return dummp.next;
}

方法 2：递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function mergeTwoLists(
  list1: ListNode | null,
  list2: ListNode | null
): ListNode | null {
  if (list1 == null) return list2;
  if (list2 == null) return list1;

  if (list1.val < list2.val) {
    list1.next = mergeTwoLists(list1.next, list2);
    return list1;
  } else {
    list2.next = mergeTwoLists(list1, list2.next);
    return list2;
  }
}

回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

方法 1：利用栈

1
2
3
4
5
6
7
8
9
10
11
12
13
function isPalindrome(head: ListNode | null): boolean {
  const stack = [];
  let p = head;
  while (!!p) {
    stack.push(p);
    p = p.next;
  }
  while (stack.length) {
    if (head.val !== stack.pop().val) return false;
    head = head.next;
  }
  return true;
}

方法 2：递归

1
2
3
4
5
6
7
8
9
10
function isPalindrome(head: ListNode | null): boolean {
  let tmp = head;
  const check = (node: ListNode | null) => {
    if (node == null) return true;
    const res = check(node.next) && tmp.val === node.val;
    tmp = tmp.next;
    return res;
  };
  return check(head);
}

方法 3：快慢指针 + 反转后边段链表

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
function isPalindrome(head: ListNode | null): boolean {
  if (head == null) return true;

  const leftHalfEnd = endOfHalf(head); // 通过快慢指针找到中点
  const rightHalfStart = reverseList(leftHalfEnd.next); // 反转后半截链表

  let p1 = head;
  let p2 = rightHalfStart;
  let result = true;
  while (result && p2 != null) {
    if (p1.val != p2.val) result = false;
    p1 = p1.next;
    p2 = p2.next;
  }

  leftHalfEnd.next = reverseList(rightHalfStart); // 将后半截被反转链表恢复
  return result;
}

function endOfHalf(head: ListNode) {
  let fast = head;
  let slow = head;
  while (fast.next && fast.next.next) {
    fast = fast.next.next;
    slow = slow.next;
  }
  return slow;
}

function reverseList(head: ListNode) {
  let prev = null;
  let current = head;
  while (!!current) {
    let nextTemp = current.next;
    current.next = prev;
    prev = current;
    current = nextTemp;
  }
  return prev;
}

环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

方法 1：快慢指针

1
2
3
4
5
6
7
8
9
10
function hasCycle(head: ListNode | null): boolean {
  let slow = head;
  let fast = head;
  while (slow && fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}

方法 2：哈希表

1
2
3
4
5
6
7
8
9
function hasCycle(head: ListNode | null): boolean {
  const nodes = new Set();
  while (head) {
    if (nodes.has(head)) return true;
    nodes.add(head);
    head = head.next;
  }
  return false;
}
 评论
评论插件加载失败
正在加载评论插件