第一周 - 链表 - 课程内容 - 《leetCode刷题》

预习内容：
课程随记：

预习内容：

课程随记：

前序（几个概念的理解）：

算法和数据结构？

参考链接：一句话+一张图理解——数据结构与算法
一句话：

相互之间存在关系的数据元素的集合就是数据结构，算法是解决特定问题的有限求解步骤。

一张图：

数据类型和数据结构？

简单理解：
数据结构 = 数据元素 + 数据关系；
数据类型 = 数据结构 + 数据操作；
基础概念（背景知识）：引用出处

数据结构：是相互之间存在一种或多种特定关系的数据元素的集合，包括逻辑结构和物理结构。
数据类型：是一个值的集合和定义在这个值集上的一组操作的总称。
抽象数据类型：是指一个数学模型以及定义在该模型上的一组操作。

总结：
数据结构是一种值的集合，这种值集＋值集上的操作就是结构类型，而结构类型是数据类型中的一种，所以数据结构属于数据类型。
数据类型和抽象数据类型的相同点在于它们具有相同的逻辑特性，不同点在于数据类型即关系数据集的逻辑特性又关系其物理特性，而抽象数据类型只关心数据集的抽象特性。

什么是数据结构（参考上述内容）

算法能力和编码能力？

链表

链表结构

概念：串结构（即线性结构），每个节点含 数据域、指针域 两个部分
查找：O(n)，插入和删除O(1) ——— 时间复杂度和空间复杂度
不适合快速的定位数据，适合动态的插入和删除

链表的实现方法

节点+指针

示例回忆：

// 1. 单链表为线性结构
// 2. 节点分为数据域和指针两部分
Class Node {
    constrctor (val, next = null) {
      this.val = val;
    this.next = next;
  }
}
function nodeList = {
    let head, next = null;
  head.text = new Node(1);
  head.next = new Node(2);
  head.next.next = new Node(3);
  head.next.next.next = new Node(4);
    let p = head;
  console.log(p)
}
nodeList()

视频代码（参考）：

Class Node {
    constrctor (val, next = null) {
      this.val = val;
    this.next = next;
  }
}

function nodeList = {
    let head = new Node(1);
  head.next = new Node(2);
  head.next.next = new Node(3);
  head.next.next.next = new Node(4);

    let p = head, ret = '';
    while(p) {
      ret = `${p.val} ->`;
    p = p.next;
  }
    ret += 'null';
    consolt.log(ret)
}

nodeList()

// 输出
1->2->3->null

双数数组

思路：定义数据域数组存放data，定义指针域数组存放指针，然后关联两个数组。
newIndex
示例回忆：

function ListCode(){
    const data = []; // 数据
    const point = []; // 指针

    // nowInd 当前节点，newIndex 新增节点
    // newVal 新增节点值
    function addNode (nowInd,newIndex,newVal) {
    // 更改新增节点指针（指向当前节点的下一个节点）
      point[newIndex] = point[nowInd];
    // 更改当前节点指针（指向新增节点）
    point[nowInd] = newIndex;
    // 赋值新增节点
    data[newIndex] = newVal;
  }

  data[3] = 's';

  addNode(3,1,'a');
  addNode(1,4,'d');
  addNode(4,7,'e');
  addNode(7,2,'b');
  addNode(2,5,'f');
  addNode(7,6,'c');

    console.log(data,point);
}

ListCode()

视频代码（参考）：

function ListCode(){
    const data = []; // 数据
    const point = []; // 指针

    // nowInd 当前节点，newIndex 新增节点
    // newVal 新增节点值
    function addNode (nowInd,newIndex,newVal) {
    // 更改新增节点指针（指向当前节点的下一个节点）
      point[newIndex] = point[nowInd];
    // 更改当前节点指针（指向新增节点）
    point[nowInd] = newIndex;
    // 赋值新增节点
    data[newIndex] = newVal;
  }

  let head = 3; // 给出目标节点下标
  data[3] = 's';

  addNode(3,1,'a');
  addNode(1,4,'d');
  addNode(4,7,'e');
  addNode(7,2,'b');
  addNode(2,5,'f');
  addNode(7,6,'c');
  // debugger;  调试用
  let p = head, ret = '';
   console.log(p);
  while(p) {
       ret +=`${data[p]} ->`
     p = point[p];
  }
  ret += 'null';

  console.log(ret);
  console.log(data);
  console.log(point);
  console.log(head);
}

ListCode()

线性结构梳理：

    let head = 3; // 给出目标节点下标
  data[3] = 's';  
    addNode(3,1,'a');
  addNode(1,4,'d');
  addNode(4,7,'e');
  addNode(7,2,'b');
  addNode(2,5,'f');

// 线性结构
{ ,3 }-->{ s,1 }-->{ a,4 }-->{ d,7 }-->{ e,2 }-->{ b,5 }-->{ f, }

// 中间添加节点
addNode(7,6,'c');

// 新增{ c, }的指针位2，替换{ e,2 }的指针为6
{ ,3 }-->{ s,1 }-->{ a,4 }-->{ d,7 }-->{ e,2 }-->{ b,5 }-->{ f, }

// 替换后
{ ,3 }-->{ s,1 }-->{ a,4 }-->{ d,7 }-->{ e,6 }-->{ c,2 }-->{ b,5 }
  -->{f, }

链表典型的应用场景

操作系统内存分配
LRU缓存淘汰算法（get、set方法的调用）

get - 获取缓存数据
set - 设置缓存数据
策略规则：后入后出，先入先出；

Map的底层实现
leetCode解析-141题===环形链表

思路：快慢指针

快慢指针: 快慢指针中的快慢指的是移动的步长，即每次向前移动速度的快慢。例如可以让快指针每次沿链表向前移动2，慢指针每次向前移动1次。

让快慢指针从链表头开始遍历，快指针向前移动两个位置，慢指针向前移动一个位置;如果快指针到达NULL，说明链表以NULL为结尾，不是循环链表。如果快指针追上慢指针，则表示出现了循环。

leetCode解析-142===环形链表 ||

思路：快慢指针

公式：慢指针的2倍速为快指针走过的路线，（左侧）慢指针走过路线借助变量的另一种表达式（右侧） 2（a+x） = （a+x）+ n（x+y） a+x = n（x+y） // 当n=1时， a = y

返回链表即返回链表的头结点；