当前位置: 首页> 学生作业 python-链表> 链表有关问题,包括合并、删除,求大神帮忙

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

* 若价格不公道,可以让提问者在平台追加赏金哦,平台是您利益的保证
已完成
链表有关问题,包括合并、删除,求大神帮忙 134****3077
赏 50元 收藏

问题详情:

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.
* 若价格不公道,可以让提问者在平台追加赏金哦,平台是您利益的保证

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

参考解决方案:

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)








此处可发布评论

    暂无评论

    竞答该问题的人有:

    公告
    更多相关问题
    Python 网考 25号九点到十二点半 有往年考试题型
    急 大学入门级python表格类作业
    编写一个爬虫,并主动对比数据,和提醒
    模拟登陆,带验证码。手动输入验证码,验证码图片下载不下来
    python项目代码详解
    python的函数对象,是自己具有call属性,还是函数对象的类,或者父类具有call属性?
    执行python程序(多进程)的时候,看cpu发现系统占用CPU率很高,但是用户占用率很低
    为什么sklearn的LinearRegression要用形如x=[[6]]的列表来作为入参?

    第一时间了解动态

    关注我们