一、链表简介
链表（Linked List）是一种常见的数据结构，用于存储和组织数据。与数组不同，链表的元素（节点）在内存中不必连续存储，而是通过指针链接在一起。
链表由多个节点组成，每个节点包含两部分：数据（存储实际的元素值）和指针（指向下一个节点的引用）。链表的第一个节点称为头节点，最后一个节点称为尾节点，尾节点的指针通常指向空值（null）。
下面是链表的一些基本特点和操作：
- 链表的优点：
- 动态性：链表的长度可以根据需要动态增长或缩小，不需要预先分配固定大小的空间。
- 插入和删除操作高效：相比数组，链表在插入和删除元素时不需要移动其他元素，只需修改指针的指向。
- 链表的缺点：
- 非随机访问：链表中的元素并不连续存储，因此无法像数组那样通过索引直接访问元素，需要遍历链表来查找指定位置的元素。
- 额外的空间开销：链表需要额外的指针来存储节点之间的链接，相比数组会占用更多的内存空间。
- 常见类型的链表：
1.单向链表（Singly Linked List）：每个节点包含一个指针，指向下一个节
- 双向链表（Doubly Linked List）：每个节点包含两个指针，分别指向前一个节点和后一个节点。
3.循环链表（Circular Linked List）：尾节点的指针指向头节点，形成一个循环。
4.常见的链表操作：
- 遍历链表：从头节点开始，依次访问每个节点。
- 插入节点：将新节点插入到链表的指定位置，涉及修改指针的指向。
- 删除节点：从链表中移除指定节点，同样需要修改指针的指向。
链表在实际应用中具有广泛的用途，例如实现栈、队列、图等数据结构，以及处理大数据集合、缓存管理等场景。
二、相关算法题：
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 的节点。
- 输入
["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
[[], [1], [3], [1, 2], [1], [1], [1]]
输出
[null, null, null, null, 2, null, 3]
解释
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addAtHead(1);
myLinkedList.addAtTail(3);
myLinkedList.addAtIndex(1, 2); // 链表变为 1->2->3
myLinkedList.get(1); // 返回 2
myLinkedList.deleteAtIndex(1); // 现在，链表变为 1->3
myLinkedList.get(1); // 返回 3
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
