[LeetCode]训练营链表

[LeetCode训练营]链表

链表的逻辑结构与存储结构Python中的单链表

一、带头结点的单链表

单链表的定义单链表的创建（尾插法）单链表的创建（头插法）插入元素删除元素 二、不带头结点的单链表 Python中的双链表

双链表的定义 Python中的循环链表

循环单链表循环双链表 链表的逻辑结构与存储结构

数据与元素之间的逻辑关系

集合、线性结构（一对一）树形结构（一对多）图结构（多对多）、

存储结构
顺序存储、链式存储、索引存储、散列存储

顺序存储（顺序表）：逻辑上相邻的元素物理位置也相邻
链式存储（单链表）：逻辑上相邻的元素物理位置不一定相邻

Python中的单链表 一、带头结点的单链表 单链表的定义

class ListNode:def __init__(self, val=0, next=None):self.val = val #val是当前节点的值self.next = next #next指向下一节点的地址

单链表的创建（尾插法）

将当前节点的next改成下一节点的地址

def Buildlink_Tail(l): #传入一个列表head = ListNode()temp = head #不要直接修改节点for elem in l:temp.next = ListNode(elem)temp = temp.nextreturn headhead = Buildlink_Tail([1, 2, 3, 4]) #储存链表的地址while head.next:head = head.nextprint(head,val) #输出每个节点中的值

单链表的创建（头插法）

用temp储存当前节点的地址，使下一节点指向当前节点

def Buildlink_Tail(l):head = ListNode()for elem in l:temp = head.nexthead.next = ListNode(elem, temp)return head

插入元素

如果插入到开头，直接将elem修改为head如果插入到中间，如插到第二位，则将第三位的地址用temp储存，再将第一位的next改成要插入的地址，最后再将第三位（elem）的next改成temp储存的地址

#在第i个位置插入elemdef Insert(i, elem): #插入到第i个元素的后面global headassert i >= 0if i == 0:elem.next = headhead = elemcur = headwhile i > 1:i -= 1cur = cur.nextif not cur:return Falsetemp = cur.nextcur.next = elemelem.next = tempreturn True

删除元素

def ListDelete(head, i): #删除i后面的那个元素assert i >= 0cur = headwhile i != 0:i -= 1cur = cur.nextif not cur.next:return Falsecur.next = cur.next.nextreturn True

二、不带头结点的单链表 Python中的双链表

可以解决单链表无法逆向索引的问题

双链表的定义

class ListNode:def __init__(self, val=0, next=None, prior):self.val = val #val是当前节点的值self.next = next #next指向下一节点的地址self.prior = piror #prior指向上一个节点的地址

Python中的循环链表 循环单链表

从一个节点出发可以找到其他任何节点

将最后一个节点的next指向head

循环双链表

从头找到尾和从尾找到头的时间复杂度都是O(1)