一、基本概念
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的；
链表存在多种形式。包括循环链表，单链表，双向链表，静态链表。
二、循环链表
2.1、基本实现和特性：
1、尾结点指针指向头结点的链表
2、可以是单链表，也可以是双链表
2.2、总结
1、优点是从链尾到链头十分方便。
2、经典问题：约瑟夫问题。
例题1：83. 删除排序链表中的重复元素https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/
三、单链表
3.1、基本实现和特性
每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域，只有一个后继结点。
3.2、重点概念
头结点， 尾结点
3.3、操作
3.3.1、建立链表：本质上就是不断的插入结点。
3.3.2、插入结点：就是申请空间，得到数据，建立链接的循环处理过程。
1、重点考虑相邻结点的指针改变，推荐画图法。
2、在指定指针的情况下插入结点，时间复杂度O（1），分为头插法和尾插两种。
3、如果没有指定指针的时候，则需要遍历先确定插入位置，再执行2，时间复杂度O（n）
4、注意头结点的插入
3.3.3、删除结点：
1、删除结点中“值为给定某个值”的结点，时间复杂度O（1）。
2、删除给定指针的结点，需要遍历前驱结点，时间复杂度O（n）。
3、注意删除头结点，尾结点，推荐画图法。
3.3.4、和数组性能比较：
3.3.5、查找结点：
1、根据指针依次查找，直到找到相应的结点（考虑多个的情况）
2、时间复杂度O（n）
四、双向链表
4.1、基本概念和特性：
单向链表只有一个方向，结点只有一个后继指针next指向后面的结点，双向链表支持两个方向，每个结点不止有一个后继指针next指向后面的结点，还有一个前驱指针prev指向前面的结点，占用更多空间的同时，插入和删除效率更高。
4.2、操作：
1、删除给定指针指向的结点，直接获取前驱结点，不需要遍历，时间复杂度为O（1），插入的情况类似删除
2、实际使用例子：java的LinkedHashMap
3、空间换时间的思想
五、静态链表
5.1、基本概念和特征：
用数组描述的链表，称为静态链表。
首先让数组的元素都是由两个数据域构成，data和cur，也就是说每一个数组的下标都要对应一个data和一个cur。
数据域data用来存放数据元素，也就是通常我们要处理的数据，而cur相当于单链表中的next指针，存放该元素的后继在数组中的下标，我们把cur叫做游标。
5.2、示例图：
六、常见面试题：
例题1：给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
示例 1:
输入: 1->1->2
输出: 1->2
示例 2:
输入: 1->1->2->3->3
输出: 1->2->3
思路：
链表中删除元素，即操作指针指向下一个元素，跳过当前元素，即完成删除操作。
时间复杂度：O（n），n为节点的个数
空间复杂度：O（1）
代码实现：
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
cur = head
while cur and cur.next:
if cur.val == cur.next.val:
cur.next = cur.next.next
else:
cur = cur.next
return head
例题2：从尾到头打印链表 https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
示例 1：
输入：head = [1,3,2]
输出：[2,3,1]
思路：
思路：循环head节点，指针移动到下一位，直到head为空
时间复杂度：O（n），n为节点的个数
空间复杂度：O（1）
代码实现：
class Solution:
def reversePrint(self, head: ListNode) -> List[int]:
res = []
while head:
res.append(head.val)
head = head.next
return res[::-1]
例题3：21. 合并两个有序链表 https://leetcode-cn.com/problems/merge-two-sorted-lists/
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = []
输出：[]
示例 3：
输入：l1 = [], l2 = [0]
输出：[0]
思路：
递归，判断l1和l2的值的大小，如果l1的val小，则l1指向l1和l2的合并后的结果，反之，则l2指向l1和l2的合并后的结果
时间复杂度：O（n），n为l1和l2的节点的个数
空间复杂度：O（1）
代码实现：
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if not l1:
return l2
if not l2:
return l1
if l1.val < l2.val:
l1.next = self.mergeTwoLists(l1.next, l2)
return l1
else:
l2.next = self.mergeTwoLists(l2.next, l1)
return l2
例题4： 24. 两两交换链表中的节点https://leetcode-cn.com/problems/swap-nodes-in-pairs/
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1：
输入：head = [1,2,3,4]
输出：[2,1,4,3]
示例 2：
输入：head = []
输出：[]
示例 3：
输入：head = [1]
输出：[1]
思路：
增加前指针指向本身，交换a，b元素，依次循环下去，返回前指针
T：O（n），n为节点的个数， S：O（1）
时间复杂度：O（n），n为节点的个数
空间复杂度：O（1）
代码实现：
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
pre, pre.next = self, head
while pre.next and pre.next.next:
a = pre.next
b = a.next
pre.next, a.next, b.next = b, b.next, a
pre = a
return self.next
撰写记录
2020.12.26-08:00:00-第一次撰写
2021.01.05-07:30:00-第二次撰写
2021.01.09-11:08:10-第三次撰写
2021.02.09-21:56:00-第四次撰写
