707-设计链表

707-设计链表

• 使用头节点和尾节点：相当于双指针
• 双指针便于插入和删除链表元素
• 定义链表的数据结构
• 实现链表元素搜索、头节点插入、尾节点插入、在链表指定位置插入元素、删除指定位置的元素

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

class MyLinkedList:
    def __init__(self):
        self.dummy = ListNode(0)   # 定义头节点
        self.tail = self.dummy     # 定义尾节点
        self.length = 0            # 定义链表长度

    def get(self, index: int) -> int:
        # 链表为空 或 索引超出链表长度
        if not self.dummy.next or index > self.length - 1:
            return -1
        # 从头开始遍历
        p = self.dummy.next
        while index:
            p = p.next
            index -= 1
        return p.val 

    def addAtHead(self, val: int) -> None:
        newnode = ListNode(val)
        if not self.dummy.next:
            self.dummy.next = newnode
            self.tail = newnode
        else:
            q = self.dummy.next
            self.dummy.next = newnode
            newnode.next = q
        self.length += 1

    def addAtTail(self, val: int) -> None:
        newnode = ListNode(val)
        self.tail.next = newnode
        self.tail = newnode
        self.length += 1

    def addAtIndex(self, index: int, val: int) -> None:
        # 直接添加到头节点
        if index < 0:
            self.addAtHead(val)
        # 添加到尾节点
        elif index == self.length:
            self.addAtTail(val)
        # 添加到链表中间
        elif index < self.length:
            p = self.dummy
            q = self.dummy.next
            # 遍历找到插入位置
            while index:
                p = p.next
                q = q.next
                index -= 1
            newnode = ListNode(val)
            p.next = newnode
            newnode.next = q
            self.length += 1

    def deleteAtIndex(self, index: int) -> None:
        if index > self.length - 1:
            return 
        p = self.dummy
        q = self.dummy.next
        # 遍历找到删除节点的前一个节点
        while index:
            p = p.next
            q = q.next
            index -= 1
        # 删除q
        if not q.next:
            p.next = None
            self.tail = p
        else:
            r = q.next
            p.next = r
        self.length -= 1