数据结构-链表

链表（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/

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