链表理论基础

链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。链表的入口节点称为链表的头结点也就是head。

image.png

链表是通过指针域的指针链接在内存中各个节点。链表中的节点在内存中不是连续分布的 ，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。

image.png

数组在定义的时候，长度就是固定的，如果想改动数组的长度，就需要重新定义一个新的数组。

链表的长度可以是不固定的，并且可以动态增删， 适合数据量不固定，频繁增删，较少查询的场景。

image.png

python中列表的定义：

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

203.移除链表元素

题目链接：

203. 移除链表元素 - 力扣（Leetcode）
给一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

收获的点：

1）对链表有了更明确的认识，是一种带着指针和存储元素的数据结构。同时相对于数组而言，链表适用于数据量不固定，需要频繁增删数据的场景，而数据在数据查询上更有优势
2）虚拟节点的设置，链表中head、next、val属性的用法

完整代码:

# 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) #添加一个虚拟头节点
        cur = dummy_head
        while (cur.next != None):
            if (cur.next.val == val):
                cur.next = cur.next.next #删除节点
            else:
                cur = cur.next
        return dummy_head.next

707.设计链表

题目链接：

707. 设计链表 - 力扣（Leetcode）
设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。

收获的点：

1） for 循环的巧妙应用，可以只把循环当作一个遍历的结构。如下最后返回索引是index下的cur。

cur = self.head.next
for _ in range(index):
  cur = cur.next

2）插入节点时，更新的思想。如图，（这里还是没有完全消化）现在的理解是 先把CD变成FD，再建立CF（不知道对不对）

image.png

    def addAtHead(self, val: int) -> None:
        new_node = Node(val) #创建新的节点
        new_node.next = self.head.next #将虚拟节点指向第一个节点的那个链条转化为新节点指向第一个节点的链条
        self.head.next = new_node #将虚拟节点指向新的节点，成功将新的节点插入到第一个节点
        self.size +=1

但是还是有一点不明白的地方是第四行：self.head.next = new_node,我感觉应该是self.head = new_node(好像也不对）

完整代码：

class Node:
    def __init__(self,x):
        self.val = x
        self.next = None
class MyLinkedList:
    def __init__(self):
        self.head = Node(0) #设置虚拟节点
        self.size = 0

    def get(self, index: int) -> int:
        if index < 0 or index >= self.size:
            return -1
        cur = self.head.next
        for _ in range(index):
            cur = cur.next
        return cur.val 

    def addAtHead(self, val: int) -> None:
        new_node = Node(val) #创建新的节点
        new_node.next = self.head.next #将虚拟节点指向第一个节点的那个链条转化为新节点指向第一个节点的链条
        self.head.next = new_node #将虚拟节点指向新的节点，成功将新的节点插入到第一个节点
        self.size +=1


    def addAtTail(self, val: int) -> None:
        cur = self.head
        while (cur.next ):
            cur = cur.next
        cur.next = Node(val)
        self.size +=1

    def addAtIndex(self, index: int, val: int) -> None:
        if index < 0:
            self.addAtHead(val)
            return
        elif index == self.size:
            self.addAtTail(val)
            return
        elif index > self.size:
            return
        else:
            pre = self.head
            while (index):
                pre = pre.next
                index -=1 
            new_node = Node(val)
            new_node.next = pre.next
            pre.next = new_node
            self.size +=1

    def deleteAtIndex(self, index: int) -> None:
        if index <0 or index >= self.size:
            return 
        pre = self.head #虚拟节点
        while (index):
            pre = pre.next
            index -=1 
        pre.next = pre.next.next
        self.size -=1 

反转链表

题目链接：

206. 反转链表 - 力扣（Leetcode）
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

看完讲解感觉很容易的样子，反转原来这么巧妙，计算机语言好像就是你想通了逻辑就好办。
这里的转换理解起来没有难度，不像前面构建链表处的转换，总感觉没有完全理解透。

完整代码：

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur = head
        pre = None
        while (cur) :
            tmp = cur.next
            cur.next = pre #反转
            pre = cur
            cur = tmp
        return pre