Skip to content

Latest commit

 

History

History
298 lines (211 loc) · 7.68 KB

05-反转链表-接口设计-算法复杂度.md

File metadata and controls

298 lines (211 loc) · 7.68 KB
Raw

反转链表 & 接口设计 & 算法复杂度

一、面试题：反转链表

Leetcode 原题：206. 反转链表。

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

进阶：链表可以选用迭代或递归方式，完成反转。你能否分别用这两种方式解决这道题？

1.迭代，栈结构

考虑的情况：

情况一：head 本身为 null。

情况二：head 只有一个节点。

情况三：至少有两个节点。

使用栈结构，来解决该问题，避免末尾节点的循环引用问题。

demo-project\03-链表\04-面试题-反转列表（迭代-栈结构）.ts

import ListNode from './ListNode'

function reverseList(head: ListNode | null): ListNode | null {
  // 情况一：head 本身为 null 的情况。
  // 情况二：head 只有一个节点。
  if (head === null || head.next === null) return head

  // 情况三：至少有两个节点。
  const stack: ListNode[] = []
  let current: ListNode | null = head
  while (current) {
    stack.push(current)
    current = current.next
  }

  const newHead: ListNode = stack.pop()!
  let newCurrent = newHead
  while (stack.length) {
    const node = stack.pop()!
    newCurrent.next = node
    newCurrent = newCurrent.next
  }

  // 避免栈中末尾节点的循环引用的问题。
  newCurrent.next = null
  return newHead
}

该方案多创建了一个数组，空间复杂度较高。不推荐。

2.迭代

考虑的情况：

情况一：head 本身为 null 的情况。

情况二：head 只有一个节点。

将上述两种情况的处理，合并为一行代码。

情况三：至少有两个节点。

处理步骤：

Ⅰ、先让 current 指向下一个节点。

  • 保留下一个节点的引用，使它可达，不会被销毁。

Ⅱ、改变 head 指向的节点为 newHead。

  • 对于第一个节点来说，指向 newHead，就是指向 null

Ⅲ、让 newHead 指向 head 节点。

  • 目的是下一次遍历时，第二步操作，可以让下一个节点，指向第一个节点。

Ⅳ、让 head 移向下一个节点，指向 current。

经过上面的步骤，可以反转一个节点。

demo-project\03-链表\05-面试题-反转列表（迭代）.ts

import ListNode from './ListNode';

function reverseList(head: ListNode | null): ListNode | null {
  if (head === null || head.next === null) return head

  let newHead: ListNode | null = null
  let current: ListNode | null = null
  while(head) {
    // 1.先让 current 指向下一个节点。目的：保留下一个节点的引用，使它可达，不会被销毁。
    current = head.next
    // 2.改变 head 指向的节点为 newHead，对于第一个节点来说，指向 newHead，就是指向 null
    head.next = newHead
    // 3.让 newHead 指向 head 节点。目的是下一次遍历时，第二步操作，可以让下一个节点，指向第一个节点。
    newHead = head
    // 4.让 head 移向下一个节点，指向 current
    head = current
  }

  return newHead
}

tsc 默认不能有隐式的 any 类型，要在 tsconfig.json 中配置。

3.递归

使用递归的方式进行反转。

先找到最后一个节点，再往前面的节点进行操作。

demo-project\03-链表\06-面试题-反转列表（递归）.ts

import ListNode from './ListNode';

function reverseList(head: ListNode | null): ListNode | null {
  if (head === null || head.next === null) return head

  // newHead 为倒数第一个节点。
  const newHead = reverseList(head.next)

  // 第一次执行此处代码，是 head 为倒数第二个节点的时候。
  head.next.next = head
  head.next = null

  return newHead
}

链表的核心，是引用（指针）的变化。

二、接口设计

为封装的链表，定义一个接口。

IList 接口

  • IStack 接口
    • ArrayStack 类
    • LinkedStack 类（自行实现）
  • IQueue 接口
    • ArrayQueue 类
    • LinkedQueue 类（自行实现）
  • ILinkedList 接口
    • LinkedList 类
    • DoubleLinkedList 类（自行实现）

demo-project\type\ilist.d.ts

export default interface IList<T> {
  peek(): T | undefined; // 返回栈顶元素但不移除
  isEmpty(): boolean; // 判断栈是否为空
  size(): number; // 获取栈的大小
  // get length(): number
}

demo-project\type\ilinkedlist.d.ts

import type IList from './ilist';

export default interface ILinkedList<T> extends IList<T> {
  append(value: T): void;
  traverse(): void;
  insert(position: number, value: T): boolean;
  removeAt(position: number): T | null
  get(position: number): T | null
  update(position: number, value: T): boolean
  indexOf(value: T): number
  remove(value: T): T | null
}

三、算法复杂度

回顾：算法是什么？

简单的说就是：解决问题的一系列步骤操作、逻辑。

算法复杂度是什么？

算法复杂度，分为“时间复杂度”和“空间复杂度”，用于表示算法的执行效率。

1.时间复杂度

🥚 案例理解：

比较：顺序查找，二分查找，两种不同算法，在查找有序数组中，给定元素的时间复杂度。

算法一般考虑“最坏”、“平均”两种情况下的时间复杂度。

假设在 10000 个元素中，进行查找。

顺序查找，时间复杂度是 O(n)。

  • 最坏：10000
  • 平均：10000 / 2

demo-project\04-算法复杂度\01-查找算法-顺序查找.ts

/**
 * @description: 顺序查找
 * @Author: ZeT1an
 * @param {number} array 有序的数组
 * @param {number} num 要查找的元素
 * @return {number} 元素的索引
 */
function sequentSearch(array: number[], num: number) {
  for (let i = 0; i < array.length; i++) {
    if (array[i] === num) {
      return i
    }
  }
  return -1
}

二分查找，时间复杂度是 O(log n)

  • 最坏：log(10000, 2)
  • 平均：log(10000, 2) / 2

demo-project\04-算法复杂度\02-查找算法-二分查找.ts

/**
 * @description: 此函数用于：二分查找
 * @Author: ZeT1an
 * @param {number} array 有序的数组
 * @param {number} num 要查找的元素
 * @return {number} 元素的索引
 */
function binarySearch(array: number[], num: number) {
  let start = 0;
  let end = array.length - 1;

  while (start <= end) {
    let mid = Math.floor((start + end) / 2);
    if (array[mid] === num) {
      return mid;
    } else if (array[mid] < num) {
      start = mid + 1;
    } else {
      end = mid - 1;
    }
  }
  return -1;
}

JavaScript 中提供了 performance，用于测试函数调用花费的时间。

demo-project\04-算法复杂度\03-测试查找算法的时间.ts

import sequentSearch from './01-查找算法-顺序查找';
import binarySearch from './02-查找算法-二分查找';

const MAX_LENGTH = 10000
const nums = new Array(MAX_LENGTH).fill(0).map((_, index) => index)
const num = MAX_LENGTH / 2

const startTime = performance.now()
const index = sequentSearch(nums, num)
const endTime = performance.now()
console.log(`sequentSearch: ${index} ${endTime - startTime}`)

const startTime = performance.now()
const index = binarySearch(nums, num)
const endTime = performance.now()
console.log(`binarySearch: ${index} ${endTime - startTime}`)

安装 hy-algokit 库，用于测试函数的调用时间，底层也是基于 performance 实现的。

demo-project\04-算法复杂度\03-测试查找算法的时间.ts

import sequentSearch from './01-查找算法-顺序查找';
import binarySearch from './02-查找算法-二分查找';

import { testOrderSearchEfficiency } from 'hy-algokit';

testOrderSearchEfficiency(sequentSearch)
testOrderSearchEfficiency(binarySearch)