一、 链表的基本操作
- 本题考察链表的基本操作：打印链表所有元素，查询指定位置的样本，插入指定位置样本，和删除指定位置样本；
- 输入：输入数据只有一组，第一行有n+1个整数，第一个整数是这行余下的整数数目n，后面是n个整数。
这一行整数是用来初始化列表的，并且输入的顺序与列表中的顺序相反，也就是说如果列表中是1、2、3那么输入的顺序是3、2、1。第二行有一个整数m，代表下面还有m行。每行有一个字符串，字符串是“get”，“insert”，“delete”，“show”中的一种。如果是“get”，代表获得第a个元素。（a从1开始计数）；如果是“delete”，代表删除第a个元素。（a从1开始计数）；如果是“insert”，则其后跟着两个整数a和e，代表在第a个位置前面插入e。（a从1开始计数） ；“show”之后没有正数，直接打印链表全部内容。 - 输出：如果获取成功，则输出该元素；如果删除成功，则输出“delete OK”；如果获取失败，则输出“get fail”；
如果删除失败，则输出“delete fail”；如果插入成功，则输出“insert OK”，否则输出“insert fail”；如果是“show”，则输出列表中的所有元素；如果列表是空的，则输出“Link list is empty”。注：所有的双引号均不输出。 - 样例输入：
3 3 2 1
21
show
delete 1
show
delete 2
show
delete 1
show
delete 2
insert 2 5
show
insert 1 5
show
insert 1 7
show
insert 2 5
show
insert 3 6
show
insert 1 8
show
get 2
解题思路：
注意插入删除位置的判断，然后是移位保持正确。
#定义链表节点
class LinkedNode:
def __init__(self, val = 0, next = None):
self.val = val
self.next = next
#定义链表基本操作
class MyLinkedList:
def __init__(self):
self._size = 0
self._dummyHead = LinkedNode(0)
#获取到第index个节点数值，如果index是非法数值直接返回-1， 注意index是从0开始的，第0个节点就是头结点
def get(self, index):
if index > (self._size - 1) or index < 0:
return -1
cur = self._dummyHead.next
while index:
cur = cur.next
index -= 1
return cur.val
#在链表最前面插入一个节点，插入完成后，新插入的节点为链表的新的头结点
def addAtHead(self, val):
newNode = LinkedNode(val)
newNode.next = self._dummyHead.next
self._dummyHead.next = newNode
self._size += 1
#在链表最后面添加一个节点
def addAtTail(self, val):
newNode = LinkedNode(val)
cur = self._dummyHead
while cur.next:
cur = cur.next
cur.next = newNode
self._size += 1
#在第index个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。
def addAtIndex(self, index, val):
if index > self._size:
return -1
if index < 0:
return -1
newNode = LinkedNode(val)
cur = self._dummyHead
while index:
cur = cur.next
index -= 1
newNode.next = cur.next
cur.next = newNode
self._size += 1
return 0
#删除第index个节点，如果index 大于等于链表的长度，直接return，注意index是从0开始的
def deleteAtIndex(self, index):
if index >= self._size or index < 0:
return -1
cur = self._dummyHead
while index:
cur = cur.next
index -= 1
tmp = cur.next
cur.next = cur.next.next
del tmp
self._size -= 1
return 0
#打印链表
def printLinkedList(self):
cur = self._dummyHead
if cur.next == None:
return -1
while cur.next:
print(cur.next.val, end = ' ')
cur = cur.next
print()
return 0
if __name__ == "__main__":
while True:
mylinklist = MyLinkedList()
try:
# 读取链表长度和链表数值
n, *nums = list(map(int, input().split()))
# 初始化链表
for i in range(n):
mylinklist.addAtHead(nums[i])
# 读取操作的个数
m = int(input())
for i in range(m):
s = input().split()
if s[0] == "show":
if mylinklist.printLinkedList() == -1:
print("Link list is empty")
if s[0] == "delete":
t = int(s[1])
if mylinklist.deleteAtIndex(t - 1) == -1:
print("delete fail")
else:
print("delete OK")
if s[0] == "insert":
t = int(s[1])
z = int(s[2])
if mylinklist.addAtIndex(t - 1, z) == -1:
print("insert fail")
else:
print("insert OK")
if s[0] == "get":
t = int(s[1])
getValue = mylinklist.get(t - 1)
if getValue == -1:
print("get fail")
else:
print(getValue)
except:
break
二、单链表反转
- 题目表述：根据一个整数序列构造一个单链表，然后将其反转。例如：原单链表为 2 3 4 5 ，反转之后为5 4 3 2
- 输入：输入包括多组测试数据，每组测试数据占一行，第一个为大于等于0的整数n，表示该单链表的长度，后面跟着n个整数，表示链表的每一个元素。整数之间用空格隔开。
- 输出： 针对每组测试数据，输出包括两行，分别是反转前和反转后的链表元素，用空格隔开。如果链表为空，则只输出一行，list is empty。
- 样例输入：
5 1 2 3 4 5
0
解题思路
单链表反转其实就是将链表中当前元素的指针指向前一个元素；中间需要使用temp保存当前元素以保证能够访问链表中下一个元素，以此迭代下去。
class LinkNode:
def __init__(self, val, next=None) -> None:
self.val = val
self.next = next
def printLinkList(node):
while node.next:
print(node.val, end=" ")
node = node.next
print(node.val)
def reverseLinkList(node):
pre = None
cur = node
temp = None
while cur:
temp = cur.next
cur.next = pre # 翻转操作
pre = cur # 更新pre 和 cur指针
cur = temp
return pre
if __name__ == "__main__":
while True:
try:
# 输入5 1 2 3 4 5，表示链表有5个节点，值分别为1 2 3 4 5
n, *nums = map(int, input().split())
except:
break
if n == 0:
print("list is empty")
continue
dummyHead = LinkNode(0) # 这里定义的头结点 是一个虚拟头结点，而不是真正的链表头结点
cur = dummyHead
for i in range(n): # 开始构造节点
cur.next = LinkNode(nums[i])
cur = cur.next
printLinkList(dummyHead.next) # 打印链表
printLinkList(reverseLinkList(dummyHead.next)) # 打印翻转后的链表
三、删除链表中的重复元素
- 题目描述：根据一个递增的整数序列构造有序单链表，删除其中的重复元素
- 输入：输入包括多组测试数据，每组测试数据占一行，第一个为大于等于0的整数n，表示该单链表的长度，后面跟着n个整数，表示链表的每一个元素。整数之间用空格隔开
- 输出：针对每组测试数据，输出包括两行，分别是删除前和删除后的链表元素，用空格隔开。如果链表为空，则只输出一行，list is empty。
解题思路
链表中连续两个节点的值相等，则前一个节点的指针指向下下个节点，再接着判断。
class LinkNode:
def __init__(self, val, next=None) -> None:
self.val = val
self.next = next
def printLinkList(node): # 打印当前链表
while node.next:
print(node.val, end=" ")
node = node.next
print(node.val)
def removeSame(head):
if not head:
return None
cur = head
while cur and cur.next:
if cur.val == cur.next.val: # 如果当前元素和下一个元素值相等
cur.next = cur.next.next # 当前元素的指针跳过下一个元素，指向下下个。
else:
cur = cur.next
return head
if __name__ == "__main__":
while True:
try:
n, *nums = map(int, input().split())
except:
break
if n == 0:
print("list is empty")
continue
dummyHead = LinkNode(0) # 这里定义的头结点 是一个虚拟头结点，而不是真正的链表头结点
cur = dummyHead
for i in range(n): # 开始构造节点
cur.next = LinkNode(nums[i])
cur = cur.next
printLinkList(dummyHead.next) # 打印链表
printLinkList(removeSame(dummyHead.next)) # 打印去重后的链表
网友评论