python - 如何合并两个链表
问题描述
我正在尝试将两个链接列表合并在一起,这个问题是我们破解编码面试的问题。问题 2.4
在分区中,我创建了两个链表 llink_A 和 llink_B。从主链接中获取值并将它们分隔在 llink_A 和 llink_B 中。我想如果我遍历 llink_A 到最后然后指向 llink_B 应该可以工作。但是当我运行程序时它不起作用。
当我运行程序时,我得到 [3, 5, 8, 5, 10, 2, 1] Linklist len: 7 [3, 5, 5, 2, 1] --> llistA [8, 10]--> llistB
class Node:
#Singly link list
def __init__(self,data = None):
self.data = data
self.next = None
class linklist:
#linkList class
def __init__(self):
self.head = None
self.size = 0
def push(self,data):
node = Node(data)# create a new node
if self.head == None: #check to see if the head node is
#empty
self.head = node # If its empty add it to the new node
self.size = 1
return
#if the head of the linklist is filled
current = self.head
while current.next is not None:#Check the current postion is
#empty
#Move to the next line if nothing is there
current = current.next
current.next = node #point self.head to a new node
self.size+=1
def lenght(self):
#note the count doesn't start at zero
cur = self.head
counter = 0
while cur is not None:
counter+=1
cur = cur.next
print('Linklist len: '+str(counter))
return counter
def printList(self):
curr = self.head
elem = []
while(curr != None):
elem.append(curr.data)
curr = curr.next
print(elem)
#1->2->3
def remove_node(self,data):
#1->2->3
curr = self.head
if curr is not None and curr.data == data:
self.head = curr.next
curr = None
#look for the node that has the data we are looking for
while curr is not None:
if curr.data == data:
break
prev = curr
curr = curr.next
#if data isn't found just reutrn
if(curr == None):
return
#allow us to unlink the nodes
prev.next = curr.next
curr = None
def partition(self,num):
#llist_A and llist_b to be continers
list_A = linklist()
list_B = linklist()
curr = self.head
# Idea: Make two seperate llink and smash them together
while curr is not None:
if curr.data <= num:
list_A.push(curr.data)
elif curr.data > num:
list_B.push(curr.data)
curr = curr.next
list_A.printList()
list_B.printList()
#Go through all of A the point the end of A to the begining
#of B
self.head = list_A.head
head_A = list_A.head
while head_A:
if head_A.next is not None:
head_A = head_A.next
head_A.next = list_B.head
head_A = head_A.next
llist = linklist()
llist.push(3)
llist.push(5)
llist.push(8)
llist.push(5)
llist.push(10)
llist.push(2)
llist.push(1)
llist.printList()
llist.lenght()
llist.partition(5)
llist.printList()
解决方案
您忘记在此循环中将 curr 更新为 curr.next :
while curr is not None:
if curr.data <= num:
llist_A.push(curr.data)
else:
llist_B.push(curr.data)
导致无限循环的原因,只需将其更新为:
while curr is not None:
if curr.data <= num:
llist_A.push(curr.data)
else:
llist_B.push(curr.data)
curr = curr.next
推荐阅读
- asp.net - .net core 使自定义中间件能够影响路由匹配
- python - 在python中将pdf转换为文本时如何保留输入顺序?
- haskell - 我无法导入 Data.Matrix
- excel-formula - 计算包含一个单词的最后 10 行
- vim - Vim - 使用搜索寄存器查找('f','t','F','T')命令
- ios - 我可以从 IBAction 中调用 UIAlertController
- javascript - 按列表中的编号/顺序查找 json 对象中的元素
- sql - 我想了解如何运行 google app-script 来提取某个州的学校信息
- c - 如何使用 C 中的 offsetof() 和指针填充结构内的数组
- node.js - 如何使用 Koa 上传文件?