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()都注释了 要详细查看的话只需打开即可。
