题目

设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。

题目详情

在链表类中实现这些功能：

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

示例

MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2);   //链表变为1-> 2-> 3
linkedList.get(1);            //返回2
linkedList.deleteAtIndex(1);  //现在链表是1-> 3
linkedList.get(1);            //返回3

提示

• 所有值都在 [1, 1000] 之内。
• 操作次数将在 [1, 1000] 之内。
• 请不要使用内置的 LinkedList 库。

解题代码

代码

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

class LinkedList(object):

	def __init__(self):
		self.head = Node(-1)

	def create(self,list):        #创建链表，给链表赋值
		head = self.head
		for i in list:
			node = Node(i)
			if head.value == -1:
				self.head = node
			head.next = node
			head = head.next

	def get_length(self):         #获取连链表的总长度
		head = self.head
		length = 0
		while head is not None:
			head = head.next
			length += 1
		return length

	def get(self,index):           #输入索引，获取其中的值，index从0开始
		head = self.head
		length = self.get_length()
		init_index = 0
		if (index < 0) or (index > length-1): return -1    #判断输入的索引是否有效
		if index == 0:
			return head.value
		while init_index <= index:                     #循环遍历链表，查找正确的索引
			if (init_index == index):
				return head.value
			head = head.next
			init_index += 1

	def addAtHead(self,val):                      #输入值，头插法
		head = self.head
		node = Node(val)
		if head.value == -1:                     #如果链表为空的状态
			self.head = node
			return
		node.next = head                        #不为空的时候遍历
		self.head = node

	def addAtTail(self,val):                   #尾插法
		head = self.head
		node = Node(val)
		if head.value == -1:                  #空链表时
			self.head = node
			return
		while head.next is not None:          #遍历到最后一个元素
			head = head.next
		head.next = node

	def addAtIndex(self,index,val):          #在任意位置插入
		head = self.head
		node = Node(val)
		init_index = 0
		length = self.get_length()
		if index > 0 and head.value == -1
			return 
		if index > length or index < 0:     #判断插入的索引是否超长或者不正规
			print("错误的索引")
			return
		if index == 0:     #头插法相当于（中间还要判断是否为空链表）
			if head.value == -1:
				self.head = node
				return
			node.next = head
			self.head = node
			return
		while head is not None and init_index <= index:     #判断插入元素后面是否有元素
			if (init_index == index):
				node.next = head
				before.next = node
			before = head
			head = head.next
			init_index += 1
		if head is None and init_index == index:
			before.next == node

	def delectAtIndex(self,index):     #删除元素
		head = self.head
		init_index = 0
		length = self.get_length()
		if index > length-1 or index < 0:
			print("错误的索引")
			return
		if index == 0:
			if head.value == -1:
				print("链表已经为空")
				return 
			head = head.next
			self.head = head
			return
		while head is not None and init_index <= index:  
			if init_index == index:
				before.next = head.next
			before = head
			head = head.next
			init_index += 1

	def printLinked(self):
		head = self.head
		while head is not None:
			print(head.value,",",end="")
			head = head.next
		print("\n")

if __name__ == '__main__':
	obj = LinkedList()
	list1 = [1,2,3,4,5,6]
	print("----------------------打印创建的链表---------------------------")
	obj.create(list1)
	obj.printLinked()
	print("----------------------打印加入头节点的链表---------------------------")
	obj.addAtHead(1)
	obj.printLinked()
	print("----------------------打印加入尾节点的链表---------------------------")
	obj.addAtTail(6)
	obj.printLinked()
	print("----------------------打印加入中间节点的链表---------------------------")
	obj.addAtIndex(0,4)
	obj.printLinked()
	print("----------------------打印删除的任意中间节点的链表---------------------------")
	obj.delectAtIndex(9)
	obj.printLinked()

运行结果

体会

在写的过程中会遇到很多问题，比如说临界值的问题，判断index是否合格，或者链表的插入是头插还是尾插，一句话，光看是发现不了问题的，只有自己动手做才会有更大的收获。