代码随想录03：链表

理论基础

• 单链表：一个数据域 + 一个指针域（指向下个节点），最后一个节点指向空。
• 双链表：一个数据域 + 两个指针域（一个指向上个节点，一个指向下个节点）。
• 循环链表：链表首位相连。

链表定义

struct ListNode {
    int val;    // 节点上存储的值
    ListNode *next; // 指向下个节点的指针
    ListNode(int x): val(x), next(NULL) {}  // 节点构造函数
};

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

删除节点

当前指针指向下下个节点，回收删除的节点内存文章源自十年又十年-https://www.bbigsun.com/406.html

添加节点

当前指针指向添加的节点，添加的节点的指针指向下个节点。文章源自十年又十年-https://www.bbigsun.com/406.html

移除链表元素

问题：删除链表中等于给定值 val 的所有节点文章源自十年又十年-https://www.bbigsun.com/406.html

示例 1：输入：head = [1,2,6,3,4,5,6], val = 6 输出：[1,2,3,4,5]文章源自十年又十年-https://www.bbigsun.com/406.html

示例 2: 输入：head = [], val =1, 输出：[]文章源自十年又十年-https://www.bbigsun.com/406.html

示例 3：输入：head = [7,7,7,7], val = 7 输出：[]文章源自十年又十年-https://www.bbigsun.com/406.html

class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        dummy_head = ListNode(next=head)    # 添加一个虚拟节点
        cur = dummy_head
        while(cur.next != None):
            if(cur.next.val == val):
                cur.next = cur.next.next    # 删除 cur.next 节点
            else:
                cur = cur.next
        return dummy_head.next

设计链表

题意：文章源自十年又十年-https://www.bbigsun.com/406.html

在链表中实现以下功能：文章源自十年又十年-https://www.bbigsun.com/406.html

• get(index)