编程实现:输入一个正整数 repeat (0<repeat<10),做 repeat 次下列运算: 输入一个正整数 n(0<n<=9)和一组(n个)整数,建立一个单向链表,再输入一个整数 x,将链表中最后一个与x相等的整数删除。输入样例: 3 (repeat=3) 5 (数据的个数n=5) 1 2 4 3 7 (5个整数) 4 (待删除整数x=4) 5 (数据的个数n=5) 2 1 5 7 5 (5个整数) 5 (待删除整数x=5) 3 (数据的个数n=3) 1 2 4 (3个整数) 100 (待删除整数x=100输出样例: size=4:1 2 3 7 size=4:2 1 5 7 size=3:1 2 4)
时间: 2024-03-14 22:45:19 浏览: 191
以下是 Python3 实现:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def delete_last_equal(head, x):
dummy = ListNode(next=head)
prev, curr = dummy, head
last_node = None
while curr:
if curr.val == x:
last_node = curr
prev.next, prev, curr = curr, curr, curr.next
if last_node:
prev.next = last_node.next
return dummy.next
repeat = int(input())
for i in range(repeat):
n = int(input())
nums = list(map(int, input().split()))
x = int(input())
head = None
for num in reversed(nums):
head = ListNode(num, head)
head = delete_last_equal(head, x)
size = 0
res = []
while head:
size += 1
res.append(str(head.val))
head = head.next
print("size={0}:{1}".format(size, " ".join(res[::-1])))
```
思路解析:
题目要求在单向链表中删除最后一个与给定整数 x 相等的节点,需要考虑到单向链表的特点,即不能直接回到前面的节点。因此我们需要用 prev、curr 两个指针遍历整个链表,prev 始终指向 curr 的前一个节点,curr 指向当前节点。如果 curr.val 等于 x,则将 last_node 指向 curr,表示找到与 x 相等的节点。遍历完后,如果 last_node 不为空,则删除 last_node 节点。
在构造链表时,我们可以利用 Python 的列表,将 n 个整数逆序插入链表中,最后得到的链表是正序的。遍历链表,统计链表长度和节点值,最后输出即可。
时间复杂度分析:
遍历链表需要 O(n) 的时间复杂度,构造链表需要 O(n) 的时间复杂度,因此总的时间复杂度为 O(n)。
阅读全文