链表的使用 python

链表是一种数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。在Python中，我们可以使用内置的数据结构`list`来创建简单列表，但实际上更底层的是`ListNode`或类似类型的链表实现。

使用链表的主要优势在于插入和删除元素的时间复杂度通常为O(1)，因为只需要修改几个链接即可，而不需要像数组那样移动大量的元素。以下是一些基本的链表操作：

1. **创建链表**:
Python没有内置链表类型，但你可以自定义一个节点类(`ListNode`)，然后构建链表。

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

2. **添加元素**:
在链表头部添加元素：

def append_to_head(head, new_val):
    new_node = ListNode(new_val)
    new_node.next = head
    return new_node

在尾部添加元素：

def append_to_tail(head, new_val):
    if not head:
        return ListNode(new_val)
    current = head
    while current.next:
        current = current.next
    current.next = ListNode(new_val)
    return head

3. **遍历链表**:
使用迭代或递归实现：

def traverse_list(head):
    curr = head
    while curr:
        print(curr.val, end=' ')
        curr = curr.next

4. **删除元素**:
删除指定值的节点（仅适用于单向链表）：

def delete_node(head, target_val):
    if not head:
        return head
    if head.val == target_val:
        return head.next
    prev = head
    curr = head.next
    while curr:
        if curr.val == target_val:
            prev.next = curr.next
            break
        prev = curr
        curr = curr.next
    return head