leetcode-LinkedList

Tony Cao2024-03-262024-10-29

链表问题

单向链表

链表的头插法和尾插法

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

    # 头插法
    def insert_at_head(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    # 尾插法
    def insert_at_tail(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

    # 打印链表（用于测试）
    def print_list(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

头插法流程

创建一个新节点 node。在节点的数据字段中插入项目。
设置新节点 node 的下一个指针，指向当前头部指向的节点。
使头部指针 head 指向新添加的节点。

尾插法流程

在列表中查找，直到到达最后一个节点。
使用要插入的项目创建一个新节点。
将最后一个节点的下一个指针设置为新创建的节点。
将新节点的下一个指针设置为 null。

判断链表是否有环 - 快慢指针法

假设有fast和slow两个指针，一个慢一个快，如果链表是有环状的，那么走的快的那个指针迟早会跟慢指针重合

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow = fast = head  # 乌龟和兔子同时从起点出发
        while fast and fast.next:
            slow = slow.next  # 乌龟走一步
            fast = fast.next.next  # 兔子走两步
            if fast is slow:  # 兔子追上乌龟（套圈），说明有环
                return True
        return False  # 访问到了链表末尾，无环

判断环形链表的公共入口 - 快慢指针法

假设有fast和slow两个指针，一个慢一个快，如果链表是有环状的，那么走的快的那个指针迟早会跟慢指针重合
当快慢指针第一次重合的时候，重新将fast指针移动到开头head位置
当fast和slow指针再次相遇的时候，则是链表的公共入口【此时slow第一次走到入口位置】

class Solution(object):
    def detectCycle(self, head):
        fast, slow = head, head
        while True:
            if not (fast and fast.next): return
            fast, slow = fast.next.next, slow.next
            if fast == slow: break
        fast = head
        while fast != slow:
            fast, slow = fast.next, slow.next
        return fast