使用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题目参考此链接
具体代码如下
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()都注释了，要详细查看的话只需打开即可。