Python程序:从链表中删除指定目标的最后一个出现位置
假设我们有一个单向链表和另一个值 called “target”,我们需要删除给定链表中 “target” 的最后一个出现位置。
因此,如果输入是 [5,4,2,6,5,2,3,2,4,5,4,7],目标为5,那么输出将为 [5, 4, 2, 6, 5, 2, 3, 2, 4, 4, 7,]。
为了解决这个问题,我们将按照以下步骤进行:
- head := node
- k := null, prev := null
- found := False
- while node is not null, do
- if value of node is same as target, then
- found := True
- prev := k
- k := node
- node := next of node
- if value of node is same as target, then
- if found is False, then
- return head
- if prev is null, then
- return next of head
- next of prev := next of the next of prev
- return head
让我们看一下以下实现以更好地理解。
更多Python相关文章,请阅读:Python 教程
示例
class ListNode:
def __init__(self, data, next = None):
self.val = data
self.next = next
def make_list(elements):
head = ListNode(elements[0])
for element in elements[1:]:
ptr = head
while ptr.next:
ptr = ptr.next
ptr.next = ListNode(element)
return head
def print_list(head):
ptr = head
print('[', end = "")
while ptr:
print(ptr.val, end = ", ")
ptr = ptr.next
print(']')
class Solution:
def solve(self, node, target):
head = node
k = None
prev = None
found = False
while node:
if node.val == target:
found = True
prev = k
k = node
node = node.next
if found == False:
return head
if not prev:
return head.next
prev.next = prev.next.next
return head
ob = Solution()
L = make_list([5,4,2,6,5,2,3,2,4,5,4,7])
target = 5
print_list(ob.solve(L, target))
输入
[5,4,2,6,5,2,3,2,4,5,4,7]
输出
[5, 4, 2, 6, 5, 2, 3, 2, 4, 4, 7, ]