使用python实现单链表

刷LeetCode题刷到了单链表，因为对python比较熟悉，因此打算用python实现一个单链表。题目要求如下：

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

LeetCode题目参考此链接

LC设计链表

具体代码如下

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


class MyLinkedList:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.head = None

    def get(self, index):
        """
        Get the value of the index-th node in the linked list. If the index is invalid, return -1.
        :type index: int
        :rtype: int
        """
        if index < 0 or index >= self.length():
            return -1
        curnode = self.head
        if index == 0:
            return curnode.value
        tag = 1
        while curnode.next:
            curnode = curnode.next
            if tag == index:
                return curnode.value
            tag += 1

    def addAtHead(self, val):
        """
        Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
        :type val: int
        :rtype: None
        """
        if self.head is None:
            curnode = Node(val)
            self.head = curnode
            # self.printLink()
            return

        curnode = Node(val)
        curnode.next = self.head
        self.head = curnode
        # self.printLink()
        return

    def addAtTail(self, val):
        """
        Append a node of value val to the last element of the linked list.
        :type val: int
        :rtype: None
        """
        if self.head is None:
            self.head = Node(val)
            # self.printLink()
            return

        curnode = self.head
        if curnode.next is None:
            curnode.next = Node(val)
            self.printLink()
            return

        while curnode.next:
            curnode = curnode.next
        curnode.next = Node(val)
        # self.printLink()
        return

    def addAtIndex(self, index, val):
        """
        Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted.
        :type index: int
        :type val: int
        :rtype: None
        """
        if index < 0 or index > self.length():
            return -1
        if index == self.length():
            self.addAtTail(val)
            return
        if index == 0:
            self.addAtHead(val)
            return

        tag = 1
        curnode = self.head
        node = Node(val)
        while curnode.next:
            if tag == index:
                node.next = curnode.next
                curnode.next = node
            curnode = curnode.next
            tag += 1
        # self.printLink()
        return

    def deleteAtIndex(self, index):
        """
        Delete the index-th node in the linked list, if the index is valid.
        :type index: int
        :rtype: None
        """
        if index < 0 or index >= self.length():
            return -1
        if index == 0:
            self.head = self.head.next
            # self.printLink()
            return

        curnode = self.head
        if index == self.length() - 1:
            while curnode.next.next is not None:
                curnode = curnode.next
            curnode.next = None
            # self.printLink()
            return

        tag = 1
        while curnode.next:
            if tag == index:
                curnode.next = curnode.next.next
            curnode = curnode.next
            tag += 1
        # self.printLink()
        return

    def length(self):
        if self.head is None:
            return 0
        length = 1
        curnode = self.head
        while curnode.next:
            length += 1
            curnode = curnode.next
        return length

    def getvalue(self):
        ele = []
        curnode = self.head
        if self.head is not None:
            for i in range(0, self.length()):
                ele.append(curnode.value)
                curnode = curnode.next
            return ele
        else:
            return -1

    def printLink(self):
        print("链表长度为:" + str(self.length()), "链表为:" + str(self.getvalue()))

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

为了清晰了解对链表每一步的操作情况，我写了getvalue（）函数。

总结

我在提交代码的时候，好几次因为超时，我就很郁闷，检查了很多遍，最后发现问题出在self.printLink()这里，（代码中我注释的那个方法，如果想要查看每一步的操作步骤，取消注释即可）

我把self.printLink()全部注释掉，所用的时长大约是3500ms，加一个self.printLink()用的时长大约是3800ms。再加一个self.printLink()就超过4000ms了。因此我直接把全部的self.printLink()都注释了，要详细查看的话只需打开即可。