本文链表维护了 head、tail、size 三个属性，功能包含增、删（删除单个和删除多个）、查、反转、清除、重写魔法方法等。详见下文代码块
后续实现企业级：哨兵节点（dummy head）

链表实现

# 节点类
class ListNode:
    # 每一个单个的节点初始化的时候数值域必须有值，指针域为None
    def __init__(self, value):
        # 数值域
        self.value = value
        # 指针域
        self.next = None

# 链表类
class LinkedList:
    """
    初始化链表类，链表类我们设置三个对象属性  头：head  尾：tail  大小：size
    注意在操作链表时需要维护这三个属性：
        让 head 始终指向链表的第一个元素，
        tail 始终指向链表的最后一个元素，
        size 始终是当前更改后链表的大小
    """
    def __init__(self, node = None):
        self.head = node
        self.tail = node
        self.size = 0
        # 节点存在 需要遍历
        if node:
            self.size = 1
            # 这里注意一个细节：
            # while判断cur.next是否是空 最后cur获取到的就是最后一个节点
            # while判断cur是否是空 最后cur获取到的就是None
            cur = node
            while cur.next:
                self.size += 1
                cur = cur.next
            self.tail = cur

    # 判空
    def is_empty(self):
        return self.head is None

    # 获取链表所有的值
    def get_values(self):
        node_values = []
        cur = self.head
        while cur:
            node_values.append(cur.value)
            cur = cur.next
        return node_values

    # 头部插入：注意要维护head、size、tail
    def prepend(self, value):
        new_node = ListNode(value)
        # 空链表需要维护tail
        if self.head is None:
            self.tail = new_node
        else:
            # 新插入节点的指针域 指向旧头节点
            new_node.next = self.head
        # 头指向新节点
        self.head = new_node
        # 维护链表大小
        self.size += 1

    # 尾部插入：注意要维护head、size、tail
    def append(self, value):
        new_node = ListNode(value)
        if self.head is None:
            # 空
            self.head = new_node
        else:
            # 非空
            self.tail.next = new_node # 旧尾节点挂上新节点
        self.tail = new_node # 更新尾指针为新节点
        self.size += 1

    # 根据值删除单个节点：注意要维护head、size、tail
    def remove(self,value):
        # 空
        if self.is_empty():
            return False

        # 情况1： 删除的是头节点
        if self.head.value == value:
            # 如果链表只有一个节点 维护tail
            if self.size == 1:
                self.head = None
                self.tail = None
            else:
                self.head = self.head.next
            self.size -= 1
            return True

        # 情况2：删除的是中间节点/尾节点
        prev = self.head
        cur = self.head.next
        while cur:
            # 找到了
            if cur.value == value:
                prev.next = cur.next
                self.size -= 1
                # 删除的是尾节点
                if cur.next is None:
                    self.tail = prev
                return True
            # 未找到 后移
            prev = cur
            cur = cur.next
        return False

    # 根据值删除所有重复节点： 注意要维护head、size、tail
    def remove_all(self,value):
        del_count = 0
        # 空
        if self.is_empty():
            return del_count

        # 情况1： 批量删除头部所有匹配节点
        while self.head and self.head.value == value:
            self.head = self.head.next
            self.size -= 1
            del_count += 1

        # 头部删空，同步清空尾指针
        if self.is_empty():
            self.tail = None
            return del_count

        # 情况2：删除的是中间节点/尾节点
        prev = self.head
        cur = self.head.next
        while cur:
            # 找到了
            if cur.value == value:
                prev.next = cur.next
                del_count += 1
                self.size -= 1
                # 删除的是尾节点
                if cur.next is None:
                    self.tail = prev
                cur = prev.next
            else:
                # 未找到 后移
                prev = cur
                cur = cur.next
        return del_count

    # 在指定位置插入元素：注意要维护head、size、tail
    def insert(self, index, value):
        # 判断是否越界
        if index < 0 or index > self.size:
            raise IndexError('index out of range')

        # 在开始节点插入
        if index == 0:
            self.prepend(value)
            return

        # 在结束节点插入
        if index == self.size:
            self.append(value)
            return

        # 在中间插入
        new_node = ListNode(value)
        cur = self.head
        for _ in range(index - 1):
            cur = cur.next
        new_node.next = cur.next
        cur.next = new_node
        self.size += 1

    # 链表反转：注意要维护head、tail
    def reverse(self):
        if self.is_empty() or self.size == 1:
            return self
        # 双指针
        prev = None
        cur = self.head
        old_first_node = self.head
        while cur:
            temp = cur.next
            cur.next = prev
            # 后移
            prev = cur
            cur = temp
        self.head = prev
        self.tail = old_first_node
        return self

    # 根据值查找元素是否存在
    def search(self, value):
        cur = self.head
        while cur:
            if cur.value == value:
                return True
            cur = cur.next
        return False

    # 清除链表
    def clear(self):
        self.head = None
        self.tail = None
        self.size = 0

    # 重写len魔法方法
    def __len__(self):
        return self.size

    # 重写str魔法方法 方法中的map和join方法详细介绍见结尾扩展知识
    def __str__(self):
        # 获取链表中所有的值
        node_values = self.get_values()
        # 1. map(str, val_list)：迭代器，把每个数字转字符串 必须要转，否则抛TypeError
        node_str_values = map(str, node_values)
        # 2. "->".join(迭代器)：直接遍历迭代器拼接，无需转列表
        return '->'.join(node_str_values)
        
    # 迭代器
    def __iter__(self):
        cur = self.head
        while cur:
            yield cur.value
            cur = cur.next 


if __name__ == '__main__':
    node1 = ListNode(2)
    node2 = ListNode(2)
    node3 = ListNode(1)
    node4 = ListNode(2)
    node5 = ListNode(3)
    node1.next = node2
    node2.next = node3
    node3.next = node4
    node4.next = node5

    ll = LinkedList(node1)
    print("初始\t", ll, "长度", len(ll))
    ll.remove(2)
    print("删第一个2\t", ll, "长度", len(ll))
    ll.remove_all(2)
    print("删除全部2\t", ll, "长度", len(ll))
    ll.insert(1, 99)
    print("下标1插入99\t", ll, "长度", len(ll))
    ll.reverse()
    print("反转链表\t", ll, "长度", len(ll))
    ll.append(666)
    print("尾部追加验证tail\t", ll, "长度", len(ll))
    print("查找99：", ll.search(99))

复杂度

map和join扩展

"""
    map方法介绍：
        语法：
            map(function, *iterables)
        参数：
            参数1: 处理函数（内置函数/自定义/lambda）
            参数2: 任何可迭代的对象（列表、元组、迭代器）
        返回值：
            map 迭代器（惰性求值，节省内存，只能遍历 1 次）
        核心作用：
            把可迭代对象里每一个元素依次传入 function 执行，批量转换数据
    join方法介绍：
        语法：
            分割字符串.join(iterable)
        调用者：
            字符串（作为拼接分隔符，'--'、'->'）
        参数：
            任意可迭代对象（列表、元组、map迭代器、生成器）
        强制要求：
            可迭代对象里的每一个元素必须是字符串类型，否则抛TypeError
        核心作用：
            用指定分隔符，把一组字符串拼成一整段字符串
"""


# ---------------------- map方法 -----------------------
# 批量转字符串
vals = [1,2,3]
str_vals = map(str, vals) # 记着返回的是迭代器
# print(next(str_vals))
# print(next(str_vals))
# print(next(str_vals))
print(list(str_vals)) # ['1', '2', '3']

# 疑问：list也能取迭代器吗
# 回答：任意迭代器（map、生成器、range、文件对象等）都能直接丢进 list()，一次性把迭代器里所有元素取出，转为普通列表。


# 自定义 lambda 处理
vals = [1,2,3]
res = map(lambda x : x**2, vals)
print(list(res)) # [1,4,9]

# 多个可迭代对象并行映射
a = [1,2]
b = [10,20]
res = map(lambda x,y: x+y, a, b)
print(list(res)) # [11,22]

# 注意点： 迭代器只能遍历一次
demo = [1,2,3]
res = map(lambda x: x**2, demo)
print(list(res)) # [1,4,9]
print(list(res)) # [] 耗尽，无元素



# ------------------------ join方法 ----------------------
# 普通列表拼接
arr = ["1","2","3"]
s = "->".join(arr)
print(s) # 1->2->3

# 配合 map 解决非字符串报错
"->".join([1,2,3]) # 报错：列表里是数字，不是字符串
"->".join(map(str, [1,2,3])) # '1->2->3' map把所有数字转字符串，再join

# 空可迭代对象返回空字符串
"->".join([]) # ""

# 常见报错原因
# 报错：int不是str
"->".join([1,2,3])
# 解决：map(str, 容器) 统一转为字符串