【链表扫盲】FROM GPT-EW帮帮网

链表是一种线性数据结构，由节点（Node）组成，每个节点包含两个部分：

数据域（data）： 存储节点值。
指针域（next）： 存储指向下一个节点的引用。

链表的最大特点是：节点在内存中不必是连续的，通过指针将节点串联在一起。

一、链表的分类：

单链表（Singly Linked List）：
- 每个节点只指向下一个节点。
- 只能从头到尾遍历。
- 结构：Node -> Node -> Node -> None
双向链表（Doubly Linked List）：
- 每个节点有两个指针，分别指向前一个节点和后一个节点。
- 可以双向遍历。
- 结构：None <- Node <-> Node <-> Node -> None
循环链表（Circular Linked List）：
- 尾节点的指针指向头节点，形成环。
- 单向循环链表和双向循环链表两种。
- 结构：Node -> Node -> Node -> (回到头节点)
带头节点的链表（Headed Linked List）：
- 头节点不存放有效数据，主要用于统一操作和简化边界情况。

二、链表的基本操作：

常见操作有插入、删除、查找、遍历、反转等。

1. 创建链表：

定义节点类：

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

2. 插入节点：

在链表头插入节点：

def insert_at_head(head, value):
    new_node = ListNode(value)
    new_node.next = head
    return new_node

在链表尾插入节点：

def insert_at_tail(head, value):
    new_node = ListNode(value)
    if not head:
        return new_node
    current = head
    while current.next:
        current = current.next
    current.next = new_node
    return head

3. 删除节点：

删除值为 target 的节点：

def delete_node(head, target):
    if not head:
        return None
    if head.value == target:
        return head.next  # 删除头节点
    current = head
    while current.next and current.next.value != target:
        current = current.next
    if current.next:
        current.next = current.next.next  # 删除节点
    return head

4. 查找节点：

查找值为 target 的节点：

def search_node(head, target):
    current = head
    while current:
        if current.value == target:
            return current
        current = current.next
    return None

5. 遍历链表：

打印链表：

def print_list(head):
    current = head
    while current:
        print(current.value, end=" -> ")
        current = current.next
    print("None")

6. 反转链表：

将链表反转：

def reverse_list(head):
    prev = None
    current = head
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    return prev

思路：
- 使用三个指针：prev（前驱）、current（当前节点）、next_node（后继节点）。
- 每次循环反转指针，将 current.next 指向 prev。
- 最终返回新的头节点（即原来的尾节点）。

三、链表的常见算法：

1. 判断链表是否有环（快慢指针法）：

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

快慢指针：
- 慢指针每次走一步，快指针每次走两步。
- 如果有环，两个指针必然相遇。
- 如果无环，快指针会先到达 None。

2. 找链表的中间节点（快慢指针法）：

def find_middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

快慢指针：
- 慢指针每次走一步，快指针每次走两步。
- 当快指针走到链表末尾时，慢指针正好在中间。

3. 合并两个有序链表：

def merge_two_lists(l1, l2):
    dummy = ListNode()
    current = dummy
    while l1 and l2:
        if l1.value < l2.value:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
        current = current.next
    current.next = l1 or l2
    return dummy.next

归并思想：
- 创建一个虚拟头节点，简化链表拼接操作。
- 每次比较两个链表的头节点，取较小值拼接到新链表。
- 合并完成后返回虚拟头节点的下一节点。

四、链表的时间复杂度分析：

操作	时间复杂度
插入头部	O(1)
插入尾部	O(n)
删除节点	O(n)
查找节点	O(n)
反转链表	O(n)
判断有环	O(n)
找中间节点	O(n)

五、链表的优缺点：

优点	缺点
动态大小：插入和删除操作效率高	随机访问困难：查找复杂度为 O(n)
节省内存：不需要预留空间	节点内存开销大：每个节点存储指针
插入删除：仅修改指针，无需大量数据移动	反转链表较复杂：涉及指针操作
适用于数据量变化频繁、插入删除较多的场景	不适用于频繁访问和查找的场景

六、总结：

链表结构灵活，插入删除操作效率高，适用于动态场景。
常用操作如反转、查找、合并、判环，都需要使用快慢指针或虚拟头节点技巧。
链表操作代码要格外注意边界条件和指针操作，避免空指针和环状结构。
理解链表的优缺点，合理选择合适的数据结构。

【链表扫盲】FROM GPT