变体有双向链表，循环链表

from llist import sllist, dllist

# 单链表
sl = sllist([1, 2, 3])
print(sl)  # 输出: [1, 2, 3]

# 双链表
dl = dllist([10, 20, 30])
print(dl)  # 输出: [10, 20, 30]

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

一个标准有效的链表是

关键点一、同时持有头尾节点的引用，好处是对于头尾的操作直接是O(1)
关键点二、虚拟头尾节点, 好处是不会存在越界问题

对应题目： https://leetcode.cn/problems/design-linked-list/submissions/

下面是一个标准的链表的实现：

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        # 初始化虚拟头尾节点
        self.head = Node()  # 虚拟头节点
        self.tail = Node()  # 虚拟尾节点
        self.head.next = self.tail  # 头节点指向尾节点
        self.size = 0  # 链表的长度

    def is_empty(self):
        return self.size == 0

    def insert_at_end(self, data):
        new_node = Node(data)
        current = self.head
        while current.next != self.tail:
            current = current.next
        current.next = new_node
        new_node.next = self.tail
        self.size += 1

    def insert_at_beginning(self, data):
        new_node = Node(data)
        new_node.next = self.head.next
        self.head.next = new_node
        self.size += 1

    def delete(self, data):
        current = self.head
        while current.next != self.tail:
            if current.next.data == data:
                current.next = current.next.next
                self.size -= 1
                return True
            current = current.next
        return False

    def search(self, data):
        current = self.head.next
        while current != self.tail:
            if current.data == data:
                return True
            current = current.next
        return False

    def update(self, old_data, new_data):
        current = self.head.next
        while current != self.tail:
            if current.data == old_data:
                current.data = new_data
                return True
            current = current.next
        return False

    def display(self):
        current = self.head.next
        while current != self.tail:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

    def list_to_linked_list(self, lst):
        for data in lst:
            self.insert_at_end(data)

# 使用示例
ll = LinkedList()

# 插入节点
ll.insert_at_end(1)
ll.insert_at_end(2)
ll.insert_at_end(3)
ll.display()  # 输出: 1 -> 2 -> 3 -> None

# 在头部插入节点
ll.insert_at_beginning(0)
ll.display()  # 输出: 0 -> 1 -> 2 -> 3 -> None

# 删除节点
ll.delete(2)
ll.display()  # 输出: 0 -> 1 -> 3 -> None

# 查找节点
print(ll.search(3))  # 输出: True
print(ll.search(4))  # 输出: False

# 更新节点
ll.update(1, 10)
ll.display()  # 输出: 0 -> 10 -> 3 -> None

# 将列表转换为链表
ll2 = LinkedList()
ll2.list_to_linked_list([4, 5, 6])
ll2.display()  # 输出: 4 -> 5 -> 6 -> None

算法

反转链表

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node

    def reverse(self):
        prev = None
        current = self.head
        while current:
            next_node = current.next
            current.next = prev
            prev = current
            current = next_node
        self.head = prev

    def display(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# 使用示例
ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
ll.display()  # 输出: 1 -> 2 -> 3 -> None
ll.reverse()
ll.display()  # 输出: 3 -> 2 -> 1 -> None

检测链表中的环

环形链表是指链表中存在一个节点指向之前某个节点的情况。检测环的方法通常使用快慢指针（Floyd’s Cycle-Finding Algorithm）。

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def has_cycle(head):
    slow = head
    fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True  # 检测到环
    return False

# 使用示例
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = head  # 创建一个环
print(has_cycle(head))  # 输出: True

合并两个有序链表

将两个有序链表合并为一个有序链表是一个常见的算法问题。

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def merge_two_sorted_lists(l1, l2):
    dummy = Node(0)
    tail = dummy

    while l1 and l2:
        if l1.data < l2.data:
            tail.next = l1
            l1 = l1.next
        else:
            tail.next = l2
            l2 = l2.next
        tail = tail.next

    tail.next = l1 if l1 else l2
    return dummy.next

# 使用示例
l1 = Node(1)
l1.next = Node(3)
l1.next.next = Node(5)

l2 = Node(2)
l2.next = Node(4)
l2.next.next = Node(6)

merged_head = merge_two_sorted_lists(l1, l2)
current = merged_head
while current:
    print(current.data, end=" -> ")
    current = current.next
print("None")  # 输出: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> None

使用一个哨兵节点 dummy 来简化代码逻辑。
遍历两个链表，将较小的节点添加到结果链表中。
当一个链表结束时，将另一个链表剩余的部分直接连接到结果链表。

删除链表中的重复节点

在一个排序的链表中，删除重复的节点，使每个元素只出现一次。

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node

    def remove_duplicates(self):
        current = self.head
        while current and current.next:
            if current.data == current.next.data:
                current.next = current.next.next
            else:
                current = current.next

    def display(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# 使用示例
ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(2)
ll.append(3)
ll.append(3)
ll.display()  # 输出: 1 -> 2 -> 2 -> 3 -> 3 -> None
ll.remove_duplicates()
ll.display()  # 输出: 1 -> 2 -> 3 -> None

查找链表中的中间节点

查找链表中间节点的方法之一是使用快慢指针。

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

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

# 使用示例
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(4)
head.next.next.next.next = Node(5)
print(find_middle(head))  # 输出: 3

slow 指针每次移动一步，fast 指针每次移动两步。
当 fast 指针到达链表末尾时，slow 指针正好位于链表的中间位置。

stayt2 / old

链表 #20

算法

反转链表

检测链表中的环

合并两个有序链表

删除链表中的重复节点

查找链表中的中间节点