链表（Linked List）的基本概念
链表是一种常见的数据结构，它由一系列节点（Node）组成。每个节点包含两部分：数据部分和指向下一个节点的指针（Pointer）。链表通过这些指针将节点按顺序连接在一起。
链表的类型
- 单链表（Singly Linked List）：每个节点只有一个指针，指向下一个节点。
- 双链表（Doubly Linked List）：每个节点有两个指针，一个指向前一个节点，一个指向下一个节点。
- 循环链表（Circular Linked List）：单链表或双链表的最后一个节点的指针又指向了链表的头节点，形成一个环形结构。
链表的基本操作
- 创建链表：首先创建头节点（Head Node），然后逐个添加后续节点。
- 插入节点
- 在头部插入：创建新节点，将新节点的指针指向原头节点，然后更新头节点为新节点。
- 在中间插入：找到要插入位置的前一个节点，创建新节点，将新节点的指针指向插入位置的节点，然后将前一个节点的指针指向新节点。
- 在尾部插入：找到链表的尾节点，创建新节点，将尾节点的指针指向新节点，并将新节点的指针设为 None。
- 删除节点
- 删除头节点：将头节点指向下一个节点，然后释放原头节点的内存。
- 删除中间节点：找到要删除节点的前一个节点，将其指针绕过要删除的节点，直接指向该节点的下一个节点，然后释放要删除节点的内存。
- 删除尾节点：找到尾节点的前一个节点，将其指针设为 None，然后释放尾节点的内存。
- 遍历链表：从链表的头节点开始，通过节点的指针依次访问每个节点，直到到达链表的尾部（指针为 None）。
链表的应用场景
- 动态数据存储：链表在需要频繁进行插入和删除操作的场景中非常有用，例如在实现一个动态大小的集合或者队列时。
- 内存管理：操作系统在管理内存分配时会使用链表来记录空闲内存块的信息。
- 多项式表示：在数学计算中，可以用链表来表示多项式，每个节点存储多项式中的一项的系数和指数。
链表的操作技巧
- 哨兵节点：可以创建一个新的节点，让其next指向头节点，从而可以简化边界的判断
- 双指针：前后双指针和快慢双指针
删除倒数第k个节点：https://leetcode.cn/problems/SLwz0R/description/
代码语言：javascript复制class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
dummy = ListNode(0)
dummy.next = head
p1 = dummy
p2 = head
for _ in range(n):
p2 = p2.next
while p2 is not None:
p1 = p1.next
p2 = p2.next
p1.next = p1.next.next
return dummy.next
