链表有关问题,包括合并、删除,求大神帮忙

*若价格不公道,可以让提问者在平台追加赏金哦,平台是您利益的保证

已完成
链表有关问题,包括合并、删除,求大神帮忙-134****3077
134****3077 1年前发布
悬赏:50.0 元

问题详情:分类: python-链表

Problem 2: transform(lst)
Given a linked list, transform it into a Python list. The head of the linked list corresponds to the left of the Python list. When the input linked list is empty, the output Python list should be empty as well.
Example: When the input linked list is 1 → 2 → 3, the output Python list should be [1,2,3] .

Problem 3: concatenate(lst1, lst2 )
Given two (possibly empty) linked lists, concatenate them such that the first list comes first.
Example: When the first input linked list lst1 is 1 → 2 → 3 and the second lst2 is 7 → 8 → 9, the output
linked list is 1 → 2 → 3 → 7 → 8 → 9.

Problem 4: removeNodesFromBeginning(lst, n)
Remove the first n nodes from a (possible empty) linked list.
Note: 0 ≤ n ≤ lst.length()
Example: Given an linked list 1 → 2 → 3 → 4 → 5 and n = 3, return the linked list 4 → 5.

Problem 5: removeNodes(lst, i, n)
Starting from the ith node in a (possibly empty) linked list, remove the next n nodes, not including the ith node.
• We say the head of the input list is the first node, i.e., i = 1.
• When i = 0, your function should start by removing the head. Note:
•n≥0
•i≥0
• i + n ≤ lst.length()
Example:let lst bealinkedlist1→2→3→4→5→6
1. Wheni=2andn=3,returnthelinkedlist1→2→6.
Explanation: The second node (i = 2) is 2. Removing the next three nodes (n = 3) means removing nodes 3, 4, and 5. The remaining ones are 1, 2, 6.
2. Wheni=0andn=3,returnthelinkedlist4→5→6.
Explanation: Since i = 0, we remove the first three nodes (n = 3) from the beginning of lst , which are 1, 2, 3. The remaining ones are 4, 5, 6.

*若价格不公道,可以让提问者在平台追加赏金哦,平台是您利益的保证。你觉得当前的价格如何呢,奉上您珍贵的一票吧

虚高0人次 适中0人次 偏低0人次

分享海报会更快解决你的问题哦!分享海报

参考答案:

无情铁手 1年前解决
已赚4091.05元

class Queue:
def __init__(self):
self.items = []

def isEmpty(self):
return self.items == []

def enqueue(self, item):
self.items.insert(0, item)

def dequeue(self):
return self.items.pop()

def size(self):
return len(self.items)

"""
Node class used for Problem 2-5
"""
class Node:
def __init__(self, data):
self.data = data
self.next = None

def getData(self):
return self.data

def getNext(self):
return self.next

def setData(self, data):
self.data = data

def setNext(self, node):
self.next = node


"""
1. Stack2 class
Implement stack data structure using queue
"""
class Stack2:
def __init__(self):
# Write your definition for __init__ here
self.items = []

def isEmpty(self):
# Write your definition for isEmpty here
return self.items == []

def push(self, item):
# Write your definition for push here
self.items.append(item)

def pop(self):
# Write your definition for pop here
if self.items:
return self.items.pop(0)
else:
print("pop() error: Stack is Empty.")
return None

def peek(self):
# Write your definition for peek here
if self.items:
return self.items[-1]
else:
print("pop() error: Stack is Empty.")
return None

def size(self):
# Write your definition for size here
return len(self.items)


"""
2. transform(lst)
Transform an unordered list into a Python list
Input: an (possibly empty) unordered list
Output: a Python list
"""
def transform(lst):
# Write your code here
res = []
if lst is None:
return res
while 1:
res.append(lst.getData())
if lst.getNext() is None: break
lst = lst.getNext()
return res


"""
3. concatenate(lst1, lst2)
Concatenate two unordered lists
Input: two (possibly empty) unordered list
Output: an unordered list
"""
def concatenate(lst1, lst2):
# Write your code here
if lst1 is None and lst2 is None:
return None
elif lst1 is None:
return lst2
elif lst2 is None:
return lst1

res = lst1
while 1:
if lst1.getNext() is None: break
lst1 = lst1.getNext()
lst1.setNext(lst2)

return res




# lst1 = [Node(1),Node(2),Node(3)]
# lst1[0].setNext(lst1[1])
# lst1[1].setNext(lst1[2])

# lst2 = [Node(7),Node(8),Node(9)]
# lst2[0].setNext(lst2[1])
# lst2[1].setNext(lst2[2])
# print(concatenate(lst1, lst2))

"""
4. removeNodesFromBeginning(lst, n)
Remove the first n nodes from an unordered list
Input:
lst -- an (possibly empty) unordered list
n -- a non-negative integer
Output: an unordred list
"""
def removeNodesFromBeginning(lst, n):
# Write your code here
if lst is None or n < 0:
return None

while n > 0:
if lst.getNext() is None: break
temp = lst
lst = lst.getNext()
temp.setNext(None)
n -= 1
if n == 0: return lst



# lst = [Node(1),Node(2),Node(3),Node(4),Node(5)]
# lst[0].setNext(lst[1])
# lst[1].setNext(lst[2])
# lst[2].setNext(lst[3])
# lst[3].setNext(lst[4])
# print(removeNodesFromBeginning(lst[0], 3))


"""
5. removeNodes(lst, i, n)
Starting from the ith node, remove the next n nodes
(not including the ith node itself).
Assume i + n <= lst.length(), i >= 0, n >= 0.
Input:
lst -- an unrdered list
i -- a non-negative integer
n -- a non-negative integer
Output: an unordred list

lst = [1, 2, 3, 4, 5]
i = 2
n = 2
return [1, 2, 5]

i = 1
n = 2
return [1, 4, 5]

i = 0
n = 2
return [3, 4, 5]
"""
def removeNodes(lst, i, n):
# Write your code here
if lst is None or n < 0 or i < 0:
return None
res = lst
left = None
right = None
idx = 0
while 1:
if i > 0 and idx == i - 1:
left = lst
if idx == i + n:
right = lst
break

if lst.getNext() is None: break
lst = lst.getNext()
idx += 1

left and left.setNext(right)

if right and left is None : return right
elif left: return res

# lst = [Node(1),Node(2),Node(3),Node(4),Node(5)]
# lst[0].setNext(lst[1])
# lst[1].setNext(lst[2])
# lst[2].setNext(lst[3])
# lst[3].setNext(lst[4])
# removeNodes(lst[0],4, 1)








此处可发布评论

评论(1

尅爱的小狗 能力:290

2021-01-27 16:03:00

加你qq没同意。
点击加载更多
客服QQ 1913284695