一矫渔、 鏈表的基本操作
- 本題考察鏈表的基本操作：打印鏈表所有元素，查詢指定位置的樣本让禀，插入指定位置樣本挑社，和刪除指定位置樣本；
- 輸入：輸入數(shù)據(jù)只有一組巡揍，第一行有n+1個(gè)整數(shù)痛阻，第一個(gè)整數(shù)是這行余下的整數(shù)數(shù)目n，后面是n個(gè)整數(shù)腮敌。
這一行整數(shù)是用來(lái)初始化列表的阱当，并且輸入的順序與列表中的順序相反，也就是說(shuō)如果列表中是1糜工、2弊添、3那么輸入的順序是3、2捌木、1油坝。第二行有一個(gè)整數(shù)m，代表下面還有m行刨裆。每行有一個(gè)字符串澈圈，字符串是“get”，“insert”帆啃，“delete”瞬女，“show”中的一種。如果是“get”努潘，代表獲得第a個(gè)元素诽偷。（a從1開始計(jì)數(shù)）；如果是“delete”慈俯，代表刪除第a個(gè)元素渤刃。（a從1開始計(jì)數(shù)）；如果是“insert”贴膘，則其后跟著兩個(gè)整數(shù)a和e卖子，代表在第a個(gè)位置前面插入e。（a從1開始計(jì)數(shù)） 刑峡；“show”之后沒(méi)有正數(shù)洋闽，直接打印鏈表全部?jī)?nèi)容玄柠。 - 輸出：如果獲取成功，則輸出該元素诫舅；如果刪除成功羽利，則輸出“delete OK”；如果獲取失敗刊懈，則輸出“get fail”这弧；
如果刪除失敗，則輸出“delete fail”虚汛；如果插入成功匾浪，則輸出“insert OK”，否則輸出“insert fail”卷哩；如果是“show”蛋辈，則輸出列表中的所有元素；如果列表是空的将谊，則輸出“Link list is empty”冷溶。注：所有的雙引號(hào)均不輸出。 - 樣例輸入：
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
解題思路：
注意插入刪除位置的判斷尊浓，然后是移位保持正確逞频。
#定義鏈表節(jié)點(diǎn)
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個(gè)節(jié)點(diǎn)數(shù)值，如果index是非法數(shù)值直接返回-1眠砾， 注意index是從0開始的虏劲，第0個(gè)節(jié)點(diǎn)就是頭結(jié)點(diǎn)
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
#在鏈表最前面插入一個(gè)節(jié)點(diǎn)，插入完成后褒颈，新插入的節(jié)點(diǎn)為鏈表的新的頭結(jié)點(diǎn)
def addAtHead(self, val):
newNode = LinkedNode(val)
newNode.next = self._dummyHead.next
self._dummyHead.next = newNode
self._size += 1
#在鏈表最后面添加一個(gè)節(jié)點(diǎn)
def addAtTail(self, val):
newNode = LinkedNode(val)
cur = self._dummyHead
while cur.next:
cur = cur.next
cur.next = newNode
self._size += 1
#在第index個(gè)節(jié)點(diǎn)之前插入一個(gè)新節(jié)點(diǎn)柒巫，例如index為0，那么新插入的節(jié)點(diǎn)為鏈表的新頭節(jié)點(diǎn)谷丸。
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個(gè)節(jié)點(diǎn)堡掏，如果index 大于等于鏈表的長(zhǎng)度，直接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:
# 讀取鏈表長(zhǎng)度和鏈表數(shù)值
n, *nums = list(map(int, input().split()))
# 初始化鏈表
for i in range(n):
mylinklist.addAtHead(nums[i])
# 讀取操作的個(gè)數(shù)
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
二泉唁、單鏈表反轉(zhuǎn)
- 題目表述：根據(jù)一個(gè)整數(shù)序列構(gòu)造一個(gè)單鏈表，然后將其反轉(zhuǎn)揩慕。例如：原單鏈表為 2 3 4 5 亭畜，反轉(zhuǎn)之后為5 4 3 2
- 輸入：輸入包括多組測(cè)試數(shù)據(jù)，每組測(cè)試數(shù)據(jù)占一行迎卤，第一個(gè)為大于等于0的整數(shù)n拴鸵，表示該單鏈表的長(zhǎng)度，后面跟著n個(gè)整數(shù)，表示鏈表的每一個(gè)元素劲藐。整數(shù)之間用空格隔開八堡。
- 輸出： 針對(duì)每組測(cè)試數(shù)據(jù)，輸出包括兩行聘芜，分別是反轉(zhuǎn)前和反轉(zhuǎn)后的鏈表元素兄渺，用空格隔開。如果鏈表為空汰现，則只輸出一行挂谍，list is empty。
- 樣例輸入：
5 1 2 3 4 5
0
解題思路
單鏈表反轉(zhuǎn)其實(shí)就是將鏈表中當(dāng)前元素的指針指向前一個(gè)元素服鹅；中間需要使用temp保存當(dāng)前元素以保證能夠訪問(wèn)鏈表中下一個(gè)元素凳兵，以此迭代下去。
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 # 翻轉(zhuǎn)操作
pre = cur # 更新pre 和 cur指針
cur = temp
return pre
if __name__ == "__main__":
while True:
try:
# 輸入5 1 2 3 4 5企软，表示鏈表有5個(gè)節(jié)點(diǎn)，值分別為1 2 3 4 5
n, *nums = map(int, input().split())
except:
break
if n == 0:
print("list is empty")
continue
dummyHead = LinkNode(0) # 這里定義的頭結(jié)點(diǎn) 是一個(gè)虛擬頭結(jié)點(diǎn)饭望，而不是真正的鏈表頭結(jié)點(diǎn)
cur = dummyHead
for i in range(n): # 開始構(gòu)造節(jié)點(diǎn)
cur.next = LinkNode(nums[i])
cur = cur.next
printLinkList(dummyHead.next) # 打印鏈表
printLinkList(reverseLinkList(dummyHead.next)) # 打印翻轉(zhuǎn)后的鏈表
三仗哨、刪除鏈表中的重復(fù)元素
- 題目描述：根據(jù)一個(gè)遞增的整數(shù)序列構(gòu)造有序單鏈表，刪除其中的重復(fù)元素
- 輸入：輸入包括多組測(cè)試數(shù)據(jù)铅辞，每組測(cè)試數(shù)據(jù)占一行厌漂，第一個(gè)為大于等于0的整數(shù)n，表示該單鏈表的長(zhǎng)度斟珊，后面跟著n個(gè)整數(shù)苇倡，表示鏈表的每一個(gè)元素。整數(shù)之間用空格隔開
- 輸出：針對(duì)每組測(cè)試數(shù)據(jù)囤踩，輸出包括兩行旨椒，分別是刪除前和刪除后的鏈表元素，用空格隔開堵漱。如果鏈表為空综慎，則只輸出一行，list is empty勤庐。
解題思路
鏈表中連續(xù)兩個(gè)節(jié)點(diǎn)的值相等示惊，則前一個(gè)節(jié)點(diǎn)的指針指向下下個(gè)節(jié)點(diǎn)，再接著判斷愉镰。
class LinkNode:
def __init__(self, val, next=None) -> None:
self.val = val
self.next = next
def printLinkList(node): # 打印當(dāng)前鏈表
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: # 如果當(dāng)前元素和下一個(gè)元素值相等
cur.next = cur.next.next # 當(dāng)前元素的指針跳過(guò)下一個(gè)元素米罚，指向下下個(gè)。
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) # 這里定義的頭結(jié)點(diǎn) 是一個(gè)虛擬頭結(jié)點(diǎn)丈探，而不是真正的鏈表頭結(jié)點(diǎn)
cur = dummyHead
for i in range(n): # 開始構(gòu)造節(jié)點(diǎn)
cur.next = LinkNode(nums[i])
cur = cur.next
printLinkList(dummyHead.next) # 打印鏈表
printLinkList(removeSame(dummyHead.next)) # 打印去重后的鏈表
