数据结构—链表

一：链表

1、数组是连续的内存空间；而链表可以不一定是连续的内存空间

2、单端链表；从前一个元素指向后一个元素

3、链表的功能

（1）访问 o(n)：数组是通过下表或者索引访问元素；链表是通过next指针以此递归的进行查询判断

（2）搜索 o(n)：从头部遍历；知道找到位置

（3）插入 o(1):

（4）删除 o(1):

4、特点

写入非常的快；但是读非常的慢{value,next}

5、链表的常用操作

class ListNode:def __init__(self, value=0, next=None):self.value = valueself.next = next#next为指向下一个节点的指针；next=None表示链表为空class LinkedList:def __init__(self):self.head = None#指向链表的第一个节点# 插入节点到链表的头部def insert_at_head(self, value):new_node = ListNode(value)#创建一个新节点；值=valuenew_node.next = self.head#将新节点的next指针指向当前的头节点self.head = new_node#更新链表的头节点# 插入节点到链表的尾部def insert_at_tail(self, value):new_node = ListNode(value)#创建一个新的节点if not self.head:#如果没有头节点self.head = new_node#新创建的节点作为头节点else:current = self.head#否则遍历链表；找到最后一个节点；将新的节点插入到最后的节点当中while current.next:current = current.nextcurrent.next = new_node# 删除链表中第一个匹配的节点def delete_node(self, value):current = self.headif not current:return# 如果要删除的节点是头节点if current.value == value:self.head = current.nextreturn# 找到要删除的节点并移除它while current.next:if current.next.value == value:current.next = current.next.nextreturncurrent = current.next# 打印链表def print_list(self):current = self.headwhile current:print(current.value, end=" -> ")current = current.nextprint("None")

二：刷题

题目203 移除链表元素
(1)思路：首先定义一个虚拟的节点dummy;这个虚拟的节点的目的就是为了防止头节点移动的时候元素丢失；然后在定义一个虚拟的节点current；这个节点的目的就是为了记录head节点移动前的位置；也是为了遍历链表；整体思路就是：如果当前链表的元素等于val;那么就跳过当前的节点继续遍历；如果当前的节点不等于目标值的话，那么就正常的进行遍历！

#初始化链表
class ListNode:def __init__(self,val=0,next=None):self.val=valself.next=next
class Solution:def removeElements(self, head: ListNode, val: int) -> ListNode:dummy=ListNode(0)dummy.next=headcurrent=dummywhile current.next:if current.next.val==val:current.next=current.next.nextelse:current=current.nextreturn dummy.next

题目206 反转链表

from typing import Optionalclass ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextclass Solution:def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:# 集成你想使用的函数，这次实现反转链表def func(head):if head is None:print(head, end="")return Noneprev = Nonecurrent = headwhile current is not None:next_node = current.nextcurrent.next = prevprev = currentcurrent = next_nodereturn prevreturn func(head)# 辅助函数：将列表转换为链表
def list_to_linkedlist(lst):if not lst:return Nonehead = ListNode(lst[0])current = headfor item in lst[1:]:current.next = ListNode(item)current = current.nextreturn head# 辅助函数：将链表转换为列表
def linkedlist_to_list(node):result = []while node:result.append(node.val)node = node.nextreturn result# 示例测试
head_list = []  # 空列表表示空链表
head = list_to_linkedlist(head_list)
solution = Solution()
reversed_head = solution.reverseList(head)
print(linkedlist_to_list(reversed_head))  # 输出: []