第二章 链表part01

day1 任务以及具体安排：https://docs.qq.com/doc/DUG9UR2ZUc3BjRUdY
day 2 任务以及具体安排：https://docs.qq.com/doc/DUGRwWXNOVEpyaVpG

Assignment

今日任务

● 链表理论基础
● 203.移除链表元素
● 707.设计链表
● 206.反转链表

详细布置

链表理论基础

建议：了解一下链接基础，以及链表和数组的区别

文章链接：https://programmercarl.com/%E9%93%BE%E8%A1%A8%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html

203.移除链表元素

建议： 本题最关键是要理解 虚拟头结点的使用技巧，这个对链表题目很重要。

题目链接/文章讲解/视频讲解：：https://programmercarl.com/0203.%E7%A7%BB%E9%99%A4%E9%93%BE%E8%A1%A8%E5%85%83%E7%B4%A0.html

707.设计链表

建议： 这是一道考察 链表综合操作的题目，不算容易，可以练一练 使用虚拟头结点

题目链接/文章讲解/视频讲解：https://programmercarl.com/0707.%E8%AE%BE%E8%AE%A1%E9%93%BE%E8%A1%A8.html

206.反转链表

题目链接/文章讲解/视频讲解：https://programmercarl.com/0206.%E7%BF%BB%E8%BD%AC%E9%93%BE%E8%A1%A8.html

Solution

1.了解一下链接基础，以及链表和数组的区别

Python，有自己的内存回收机制，就不用自己手动释放内存
链表和数组都是用来存储数据的常用数据结构，但它们在内存分配、性能和操作上有着本质的区别。下面是链表和数组之间的一些主要区别：（转自Chatgpt4）

内存分配

• 数组：在内存中占用一段连续的空间。当声明数组大小时，就需要知道所需的最大容量，并且一旦分配，大小通常不能改变（静态数组）。这意味着可能会有未使用的内存空间，或者在数组填满时无法添加更多元素。
• 链表：由一系列节点组成，每个节点包含数据部分和指向下一个节点的指针。节点在内存中可以分散存储，不需要占用连续的空间。这允许在不重新分配整个数据结构的情况下动态增加或减少元素。

性能

• 访问元素：数组支持随机访问，这意味着可以直接通过索引以常数时间（O(1)）访问任何元素。链表不支持随机访问，访问特定元素需要从头开始遍历，平均时间复杂度为O(n)。
• 插入和删除：在数组中插入或删除元素特别是在数组的开始或中间，通常需要移动元素来维护连续的内存，这可能是一个耗时的操作（最坏情况下为O(n)）。而在链表中，添加或删除节点只需要改变相邻节点的指针，时间复杂度为O(1)，如果你已经定位到了要插入或删除节点的位置。

使用场景

• 数组：适用于需要高效随机访问元素的场景。如果你事先知道数据量的大小，或者数据量变化不大，数组是一个好的选择。
• 链表：适合于数据量未知或需要频繁执行添加和删除操作的场景。链表的灵活性使其在需要动态内存分配时非常有用。

其他考虑

• 内存使用：虽然链表在插入和删除时更高效，但每个节点都需要额外的空间存储指针，这意味着链表的内存效率通常低于紧凑存储的数组。
• 缓存局部性：由于数组在内存中是连续存储的，它们能更好地利用CPU缓存，提高访问速度。链表的分散存储可能导致较差的缓存局部性，降低访问速度。

根据应用场景的不同，选择最合适的数据结构非常重要。

203.移除链表元素

class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        # 基本情况：如果列表为空，则返回None
        if not head:
            return None
        
        # 递归步骤：处理列表的其余部分，并更新当前节点的下一个指针
        head.next = self.removeElements(head.next, val)
        
        # 决策：如果当前节点的值等于val，则跳过它
        if head.val == val:
            return head.next
        else:
            return head

707.设计链表

class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None
class MyLinkedList:

    def __init__(self):
        self.size = 0
        self.head = ListNode(0)

    def get(self, index: int) -> int:
        if index < 0 or index >= self.size:
            return -1

        cur = self.head
        for i in range(index+1):
            cur = cur.next
        return cur.val

    def addAtHead(self, val: int) -> None:
        self.addAtIndex(0, val)##0是开头的位置

    def addAtTail(self, val: int) -> None:
        self.addAtIndex(self.size, val)

    def addAtIndex(self, index: int, val: int) -> None:
        if index > self.size:
            return
        if index < 0:
            index = 0
            
        self.size += 1
        cur = self.head
        for i in range(index):
            cur = cur.next
        add = ListNode(val)
        add.next = cur.next
        cur.next = add

    def deleteAtIndex(self, index: int) -> None:
        if index < 0 or index >= self.size:
            return

        self.size -= 1
        cur = self.head
        for i in range(index):
            cur = cur.next
        cur.next = cur.next.next

206.反转链表
容易在直接把指针反转过来，难在不好想

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        cur=head
        pre=None
        while cur:
            temp=cur.next
            cur.next=pre
            pre=cur
            cur=temp
        return pre