leetcode-链表——设计链表（二）

在链表类中实现这些功能：
get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。
deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

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


class MyLinkedList(object):
    def __init__(self):
        self.root = Node()
        self.root.next = None
        self.length = 0
        self.tail_node = None

    def __len__(self):
        return self.length

    def head_node(self):
        return self.root.next

    def get(self, index):
        head = self.head_node()
        i = 0
        while i < self.length:
            if index == i:
                return head.val
            head = head.next
            i += 1

    def addAtHead(self, val):
        node = Node(val)
        if self.head_node() is None:
            self.root.next = node
            self.tail_node = node
        else:
            head = self.head_node()
            self.root.next = node
            node.next = head
        self.length += 1

    def addAtTail(self, val):
        node = Node(val)
        tail_node = self.tail_node
        if not self.tail_node:
            self.tail_node = node
            self.root.next = node
        else:
            tail_node.next = node
        self.tail_node = node
        self.length += 1

    def addAtIndex(self, index, val):
        if index <= 0:
            self.addAtHead(val)
        elif index == self.length:
            self.addAtTail(val)
        elif index > 0 and index < self.length:
            pre = self.root.next
            count = 0
            while count < index - 1:
                count += 1
                pre = pre.next
            node = Node(val)
            pre.next = node
            self.length += 1

    def deleteAtIndex(self, index):
        pre = self.head_node()
        if self.length == 0:
            return
        elif index == 0:
            self.root.next = pre.next
        elif index < self.length and index > 0:
            count = 0
            while count < index:
                count += 1
            pre.next = pre.next.next
            if not pre.next:
                self.tail_node = pre
            self.length -= 1


linkedList = MyLinkedList()
print(linkedList.addAtTail(4))
print(linkedList.addAtHead(1))
print(linkedList.addAtHead(2))
print(linkedList.addAtTail(3))
print(linkedList.addAtIndex(0, 8))
print(linkedList.deleteAtIndex(0))
print(linkedList.get(0))

最后编辑于：2020.10.10 15:18:40