⭐ Key 1:线性表是指各数据元素间保持“1对1”关系的数据结构
⭐ Key 2:线性表分为顺序表(数组)和链表，分别通过元素相邻和保存指针域的方式来实现“1对1”
顺序实现和链式实现
顺序存储：按顺序放在一起，相邻元素 通过内存地址相邻产生联系 ”随机存取“。（随机存取的含义是 读取操作复杂度o(1),随机读取）
链式存储：元素随机放置在内存中任意 位置，每个元素除了存放数 据，也保存了其相邻元素的 内存地址来实现线性关系 ”顺序存取“ （顺序存取的含义是，读取及存储时都需要按顺序遍历到尾节点，复杂度o(n)）
链式存储的节点包括：数据域：存放实际数据 指针域:存放后续节点地址
⭐ Key 1:顺序表中增加和删除一个元素将导致该位置后的元素前移或后移，复杂度为O(n)
⭐ Key 2:单链表增加和删除元素虽然不用移动元素，但需先找到其前驱结点，复杂度为O(n)
⭐ Key 3:若线性表需要频繁更新元素 -> 选择用顺序表实现(数组)
⭐ Key 4:若线性表需要频繁插入删除元素 -> 选择用链式表实现
给定长度为 n 的线性表，查找值为 v 的元素 顺序表和链表都一样，需要(最坏)从头到尾遍历 => 时间复杂度O(n)
顺序表：给定长度为 n 的顺序表，在指定位置 i 插入一个新元素 给定长度为 n 的顺序表，删除位置 i 的元素
时间复杂度：需要将位置 i 到位置 n-1 的所有元素都向后或向前挪一格 在最坏情况(i=0)下，需要挪动全部的 n 个元素 => 时间复杂度为O(n)
空间复杂度：无需利用额外空间 => 空间复杂度为O(1)
给定长度为 n 的单链表，在第 i 个结点插入一个新元素 头 尾
插入完成后新元素是链表的第 i 个结点
• 首先需要从头结点开始逐个向后找 i-1 次 => 时间复杂度为O(n)
• 找到后插入只需要修改第 i-1 个结点和待插入结点的 [后继结点地址] 即可 => O(1)
• 无需利用额外空间 => 空间复杂度为O(1)
给定长度为 n 的单链表，删除第 i 个结点
• 无需利用额外空间 => 空间复杂度为O(1)
• 需要移动到第 i 个结点的前驱结点，最坏情况下移动n-1次 => 时间复杂度为 O(n)
• 修改前驱结点的后继指针 => O(1)
给定长度为 n 的顺序表，更新位置 i 的元素
顺序表：无论 i 的值如何，都可以通过 i 直接访问位置 i 元素，将其更新为 v’=> 时间复杂度 为O(1) => 随机存取
单链表：
• 需要从头结点开始 one-by-one 找到第 i 个结点才能访问并更新它 => 顺序存取 • 最坏情况遍历整个链表 => 时间复杂度为 O(n)
线性表的集合式合并:只合并不同元素
设A表长度为n， A: 7, 5, 3, 11 ,
B表长度为m，B: 2, 7, 6, 3
合并为： C: 7, 5, 3, 11, 2, 6
• 对于B表中的每个元素，都需要先判断其是否已经存在A里 => O(mn)
• 如果存在，无需插入，如果不存在，将其插入在A的末尾 => O(1)
• 总时间复杂度为 O(mn)
• 空间复杂度呢? • 顺序表:O(m+n)
• 链表:O(1)
合并两个有序顺序表
• 设A表长度为n, B表长度为m
• 先预留结果表空间:n+m个元素
• 从表头开始同时逐个访问A表和B表元素，将当前位置上较小者放入结果表并后移一位
• 总时间复杂度为 O(m+n)
• 空间复杂度为 O(m+n)
⭐ Key 1:合并两个有序表:逐一比较两表当前元素，将正确的元素添加进结果表并移动游标
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
nums1[m:] = nums2
nums1.sort()
复杂度分析
时间复杂度：O((m+n)log(m+n))。
排序序列长度为 m+n，套用快速排序的时间复杂度即可，平均情况为 O((m+n)log(m+n))。
空间复杂度：O(log(m+n))。
排序序列长度为 m+n，套用快速排序的空间复杂度即可，平均情况为 O(log(m+n))。
算法
方法一没有利用数组 nums1与 nums2已经被排序的性质。为了利用这一性质，我们可以使用双指针方法。这一方法将两个数组看作队列，每次从两个数组头部取出比较小的数字放到结果中。如下面的动画所示：
我们为两个数组分别设置一个指针 p1 与 p2 来作为队列的头部指针。代码实现如下：
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
sorted = []
p1, p2 = 0, 0
while p1 < m or p2 < n:
if p1 == m:
sorted.append(nums2[p2])
p2 += 1
elif p2 == n:
sorted.append(nums1[p1])
p1 += 1
elif nums1[p1] < nums2[p2]:
sorted.append(nums1[p1])
p1 += 1
else:
sorted.append(nums2[p2])
p2 += 1
nums1[:] = sorted
复杂度分析
时间复杂度：O(m+n)。 指针移动单调递增，最多移动 m+n 次，因此时间复杂度为 O(m+n)。
空间复杂度：O(m+n)。 需要建立长度为 m+n 的中间数组 sorted。
算法
方法二中，之所以要使用临时变量，是因为如果直接合并到数组 nums1中，nums1中的元素可能会在取出之前被覆盖。那么如何直接避免覆盖nums1中的元素呢？观察可知，nums1的后半部分是空的，可以直接覆盖而不会影响结果。因此可以指针设置为从后向前遍历，每次取两者之中的较大者放进 nums1的最后面。
严格来说，在此遍历过程中的任意一个时刻，nums1 数组中有 m-p1-1个元素被放入nums1的后半部，nums2数组中有 n-p2-1个元素被放入nums1的后半部，而在指针 p1 的后面，nums1数组有 m+n-p1-1个位置。由于m + n - p1 - 1 >= m − p1−1 +n −p2 −1 等价于 p2 ≥−1 永远成立，因此 p1 后面的位置永远足够容纳被插入的元素，不会产生 p1 的元素被覆盖的情况。
实现代码如下：
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
p1, p2 = m - 1, n - 1
tail = m + n - 1
while p1 >= 0 or p2 >= 0:
if p1 == -1:
nums1[tail] = nums2[p2]
p2 -= 1
elif p2 == -1:
nums1[tail] = nums1[p1]
p1 -= 1
elif nums1[p1] > nums2[p2]:
nums1[tail] = nums1[p1]
p1 -= 1
else:
nums1[tail] = nums2[p2]
p2 -= 1
tail -= 1
复杂度分析
时间复杂度：O(m+n)。
指针移动单调递减，最多移动 m+n 次，因此时间复杂度为 O(m+n)。
空间复杂度：O(1)。
直接对数组 nums1 原地修改，不需要额外空间。
理解以下名词: 理解以下关键代码行: • 顺序表与链表 • 随机存取与顺序存取 • 数据域和指针域 • 前驱结点、后继结点 • 头结点(dummy) • 单链表定位前驱结点 • 单链表插入结点时，修改指针域的顺序 • 单链表删除结点 • 合并有序单链表时，返回头结点指针域 熟悉以下过程及其复杂度: 熟练以下题型: • 顺序表/链表定位一个元素 • 顺序表/链表插入一个元素 • 顺序表/链表删除一个元素 • 合并两个有序顺序表 • *合并两个有序链表