一、链表简介
链表（Linked List）是一种常见的数据结构，用于存储和组织数据。与数组不同，链表的元素（节点）在内存中不必连续存储，而是通过指针链接在一起。
链表由多个节点组成，每个节点包含两部分：数据（存储实际的元素值）和指针（指向下一个节点的引用）。链表的第一个节点称为头节点，最后一个节点称为尾节点，尾节点的指针通常指向空值（null）。
下面是链表的一些基本特点和操作：
-
链表的优点：
- 动态性：链表的长度可以根据需要动态增长或缩小，不需要预先分配固定大小的空间。
- 插入和删除操作高效：相比数组，链表在插入和删除元素时不需要移动其他元素，只需修改指针的指向。
-
链表的缺点：
- 非随机访问：链表中的元素并不连续存储，因此无法像数组那样通过索引直接访问元素，需要遍历链表来查找指定位置的元素。
- 额外的空间开销：链表需要额外的指针来存储节点之间的链接，相比数组会占用更多的内存空间。
-
常见类型的链表：
- 单向链表（Singly Linked List）：每个节点包含一个指针，指向下一个节
- 双向链表（Doubly Linked List）：每个节点包含两个指针，分别指向前一个节点和后一个节点。
- 循环链表（Circular Linked List）：尾节点的指针指向头节点，形成一个循环。
- 单向链表（Singly Linked List）：每个节点包含一个指针，指向下一个节
-
常见的链表操作：
- 遍历链表：从头节点开始，依次访问每个节点。
- 插入节点：将新节点插入到链表的指定位置，涉及修改指针的指向。
- 删除节点：从链表中移除指定节点，同样需要修改指针的指向。
链表在实际应用中具有广泛的用途，例如实现栈、队列、图等数据结构，以及处理大数据集合、缓存管理等场景。
二、相关算法题：
1.移除链表元素
给你一个链表的头节点
head和一个整数val，请你删除链表中所有满足Node.val == val的节点，并返回 新的头节点 。输入：head = [1,2,6,3,4,5,6], val = 6 输出：[1,2,3,4,5]
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
# 创建虚拟头部节点以简化删除过程
dummy_head = ListNode(next = head)
# 定义当前节点
current=dummy_head
while current.next: # 只要当前节点有后继就循环
if current.next.val==val:
current.next=current.next.next
else:
current=current.next
reuturn dummy_head.next
2.设计链表
你可以选择使用单链表或者双链表，设计并实现自己的链表。
单链表中的节点应该具备两个属性：
val和next。val是当前节点的值，next是指向下一个节点的指针/引用。如果是双向链表，则还需要属性
prev以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。实现
MyLinkedList类：
MyLinkedList()初始化MyLinkedList对象。int get(int index)获取链表中下标为index的节点的值。如果下标无效，则返回-1。void addAtHead(int val)将一个值为val的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。void addAtTail(int val)将一个值为val的节点追加到链表中作为链表的最后一个元素。void addAtIndex(int index, int val)将一个值为val的节点插入到链表中下标为index的节点之前。如果index等于链表的长度，那么该节点会被追加到链表的末尾。如果index比长度更大，该节点将 不会插入 到链表中。void deleteAtIndex(int index)如果下标有效，则删除链表中下标为index的节点。
class ListNode:
def __init__(self,val=0,next=None):
self.val=val
self.next=next
class MyLinkedList:
def __init__(self):
self.dummy_head = ListNode()
self.size = 0
def get(self, index: int) -> int:
if index<0 or index>=self.size:
return -1
current=self.dummy_head.next
for i in range(index):
currtent=current.next
print(currtent.val)
return current.val
def addAtHead(self, val: int) -> None:
self.dummy_head.next=ListNode(val,self.dummy_head.next)
self.size+=1
def addAtTail(self, val: int) -> None:
current = self.dummy_head
while current.next:
current=current.next
current.next=ListNode(val)
self.size+=1
def addAtIndex(self, index: int, val: int) -> None:
if index <0 or index >self.size:
return
current=self.dummy_head
for i in range(index):
current=current.next
current.next=ListNode(val,current.next)
self.size+=1
def deleteAtIndex(self, index: int) -> None:
if index <0 or index >=self.size:
return
current=self.dummy_head
for i in range(index):
current=current.next
current.next=current.next.next
self.size-=1
# Your MyLinkedList object will be instantiated and called as such:
obj = MyLinkedList()
obj.addAtHead(1)
obj.addAtTail(3)
obj.addAtIndex(1,2)
obj.get(1)
obj.deleteAtIndex(1)
obj.get(1)
# ["MyLinkedList","addAtHead","addAtTail","addAtIndex","get","deleteAtIndex","get"]
# [[],[1],[3],[1,2],[1],[1],[1]]3.反转链表
给你单链表的头节点
head，请你反转链表，并返回反转后的链表。输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None,pre=None):
self.val = val
self.next = next
class Solution:
def reverseList(head):
cur = head
pre=None
while cur:
temp=cur.next
cur.next=pre
pre=cur
cur=temp
return pre
