合并 python 中的两个排序链表并返回一个新的 linked_list 而不更改任何一个输入链表
Merging two sorted linked lists in python and returning a new linked_list without changing either of input linked lists
正如标题所说，我想将两个已排序的链表合并成一个新的链表并return它。因此，例如，如果 linked_list_1 有 2 个节点，其值为 1 和 5 而linked_list_2 有 1 个值为 2 的节点，我想 return 一个具有以下值的新链表： 1, 2, 5.
我解决这个问题的逻辑是比较linked_list_1的节点数据和linked_list_2的节点数据，从每个linked_list的头部开始，然后添加节点我想要 return 的 linked_list 的最小数据。我继续这样做并移动 linked_list_1 和 linked_list_2，直到来自 linked_list 的节点是 None。一旦它是 None，我将剩余节点（来自 linked_list_1 或 linked_list_2）添加到我想要 return.[=13 的新 linked_list =]
这是我写的代码：
class Node:
def __init__(self, data=None, next_node=None):
self.data = data
self.next = next_node
def __str__(self):
return str(self.data)
class LinkedList:
def __init__(self):
self.length = 0
self.head = None
def print_list(self):
node = self.head
while node is not None:
print(node, end=' ')
node = node.next
print('')
def add_at_head(self, node):
node.next = self.head
self.head = node
self.length += 1
def remove_node_after(self, node):
if node.next is not None:
temp = node.next
node.next = node.next.next
temp.next = None
self.length -= 1
def remove_first_node(self):
if self.head is None:
return
temp = self.head
self.head = self.head.next
temp.next = None
self.length -= 1
def print_backward(self):
def print_nodes_backward(node):
if node.next is not None:
print_nodes_backward(node.next)
if node is not None:
print(node, end=' ')
if self.head is not None:
print_nodes_backward(self.head)
print('')
def merge_linked_lists(linked_list_1, linked_list_2):
# merge two sorted linked lists into a new linked list
ll = LinkedList()
node1 = linked_list_1.head
node2 = linked_list_2.head
if node1 is None:
return linked_list_2.print_list()
if node2 is None:
return linked_list_1.print_list()
while node1 is not None and node2 is not None:
if node1.data == node2.data:
ll.add_at_head(node1)
ll.add_at_head(node2)
node1 = node1.next
node2 = node2.next
elif node1.data < node2.data:
ll.add_at_head(node1)
node1 = node1.next
else:
ll.add_at_head(node2)
node2 = node2.next
while node1 is not None:
ll.add_at_head(node1)
node1 = node1.next
while node2 is not None:
ll.add_at_head(node2)
node2 = node2.next
return ll.print_backward()
在 运行 代码之后，我遇到了一个无限循环，我不确定为什么会这样。非常感谢任何帮助。
原因是因为你的add_at_head()实际上是在修改当前正在添加的节点的.next。
因此，当你在第 3 个链表中添加一个已经存在 .next 的节点时， .next 被覆盖，导致第 3 个无限循环，而当它一直链接到链表中的第一个节点和新节点一起，已经有一个 .next
要解决该问题，您可以在 add_at_head() 中创建正在处理的节点的副本，这应该可以解决该问题，如下所示：
def add_at_head(self, node):
new_node = Node(node.data)
new_node.next = self.head
self.head = new_node
self.length += 1
class Node:
def __init__(self, data=None, next_node=None):
self.data = data
self.next = next_node
def __str__(self):
return str(self.data)
class LinkedList:
def __init__(self):
self.length = 0
self.head = None
# add next node at this position
self.add_at_this_position = None
def print_list(self):
node = self.head
while node is not None:
print(node, end=' ')
node = node.next
print('')
def add_at_head(self, node):
# if head is none create a new node
if self.head == None:
self.head = Node(data=node.data)
self.add_at_this_position = self.head
return
# adding a new node
self.add_at_this_position.next = Node(data=node.data)
self.add_at_this_position = self.add_at_this_position.next
self.length += 1
def remove_node_after(self, node):
if node.next is not None:
temp = node.next
node.next = node.next.next
temp.next = None
self.length -= 1
def remove_first_node(self):
if self.head is None:
return
temp = self.head
self.head = self.head.next
temp.next = None
self.length -= 1
def print_backward(self):
def print_nodes_backward(node):
if node.next is not None:
print_nodes_backward(node.next)
if node is not None:
print(node, end=' ')
if self.head is not None:
print_nodes_backward(self.head)
print('')
def merge_linked_lists(linked_list_1, linked_list_2):
# merge two sorted linked lists into a new linked list
ll = LinkedList()
node1 = linked_list_1.head
node2 = linked_list_2.head
if node1 is None:
return linked_list_2.print_list()
if node2 is None:
return linked_list_1.print_list()
while node1 is not None and node2 is not None:
if node1.data == node2.data:
ll.add_at_head(node1)
ll.add_at_head(node2)
node1 = node1.next
node2 = node2.next
elif node1.data < node2.data:
ll.add_at_head(node1)
node1 = node1.next
else:
ll.add_at_head(node2)
node2 = node2.next
while node1 is not None:
ll.add_at_head(node1)
node1 = node1.next
while node2 is not None:
ll.add_at_head(node2)
node2 = node2.next
return ll.print_backward()
def create_linked_list(data):
ll = LinkedList()
for i in data:
node = Node(data=i)
ll.add_at_head(node)
return ll
linked_list_1 = create_linked_list([1,7, 8])
linked_list_2 = create_linked_list([5, 6, 11])
merge_linked_lists(linked_list_1, linked_list_2)
您需要更改 add_at_head 功能，一切都会正常。
正如标题所说，我想将两个已排序的链表合并成一个新的链表并return它。因此，例如，如果 linked_list_1 有 2 个节点，其值为 1 和 5 而linked_list_2 有 1 个值为 2 的节点，我想 return 一个具有以下值的新链表： 1, 2, 5.
我解决这个问题的逻辑是比较linked_list_1的节点数据和linked_list_2的节点数据，从每个linked_list的头部开始，然后添加节点我想要 return 的 linked_list 的最小数据。我继续这样做并移动 linked_list_1 和 linked_list_2，直到来自 linked_list 的节点是 None。一旦它是 None，我将剩余节点（来自 linked_list_1 或 linked_list_2）添加到我想要 return.[=13 的新 linked_list =]
这是我写的代码：
class Node:
def __init__(self, data=None, next_node=None):
self.data = data
self.next = next_node
def __str__(self):
return str(self.data)
class LinkedList:
def __init__(self):
self.length = 0
self.head = None
def print_list(self):
node = self.head
while node is not None:
print(node, end=' ')
node = node.next
print('')
def add_at_head(self, node):
node.next = self.head
self.head = node
self.length += 1
def remove_node_after(self, node):
if node.next is not None:
temp = node.next
node.next = node.next.next
temp.next = None
self.length -= 1
def remove_first_node(self):
if self.head is None:
return
temp = self.head
self.head = self.head.next
temp.next = None
self.length -= 1
def print_backward(self):
def print_nodes_backward(node):
if node.next is not None:
print_nodes_backward(node.next)
if node is not None:
print(node, end=' ')
if self.head is not None:
print_nodes_backward(self.head)
print('')
def merge_linked_lists(linked_list_1, linked_list_2):
# merge two sorted linked lists into a new linked list
ll = LinkedList()
node1 = linked_list_1.head
node2 = linked_list_2.head
if node1 is None:
return linked_list_2.print_list()
if node2 is None:
return linked_list_1.print_list()
while node1 is not None and node2 is not None:
if node1.data == node2.data:
ll.add_at_head(node1)
ll.add_at_head(node2)
node1 = node1.next
node2 = node2.next
elif node1.data < node2.data:
ll.add_at_head(node1)
node1 = node1.next
else:
ll.add_at_head(node2)
node2 = node2.next
while node1 is not None:
ll.add_at_head(node1)
node1 = node1.next
while node2 is not None:
ll.add_at_head(node2)
node2 = node2.next
return ll.print_backward()
在 运行 代码之后，我遇到了一个无限循环，我不确定为什么会这样。非常感谢任何帮助。
原因是因为你的add_at_head()实际上是在修改当前正在添加的节点的.next。
因此，当你在第 3 个链表中添加一个已经存在 .next 的节点时， .next 被覆盖，导致第 3 个无限循环，而当它一直链接到链表中的第一个节点和新节点一起，已经有一个 .next
要解决该问题，您可以在 add_at_head() 中创建正在处理的节点的副本，这应该可以解决该问题，如下所示：
def add_at_head(self, node):
new_node = Node(node.data)
new_node.next = self.head
self.head = new_node
self.length += 1
class Node:
def __init__(self, data=None, next_node=None):
self.data = data
self.next = next_node
def __str__(self):
return str(self.data)
class LinkedList:
def __init__(self):
self.length = 0
self.head = None
# add next node at this position
self.add_at_this_position = None
def print_list(self):
node = self.head
while node is not None:
print(node, end=' ')
node = node.next
print('')
def add_at_head(self, node):
# if head is none create a new node
if self.head == None:
self.head = Node(data=node.data)
self.add_at_this_position = self.head
return
# adding a new node
self.add_at_this_position.next = Node(data=node.data)
self.add_at_this_position = self.add_at_this_position.next
self.length += 1
def remove_node_after(self, node):
if node.next is not None:
temp = node.next
node.next = node.next.next
temp.next = None
self.length -= 1
def remove_first_node(self):
if self.head is None:
return
temp = self.head
self.head = self.head.next
temp.next = None
self.length -= 1
def print_backward(self):
def print_nodes_backward(node):
if node.next is not None:
print_nodes_backward(node.next)
if node is not None:
print(node, end=' ')
if self.head is not None:
print_nodes_backward(self.head)
print('')
def merge_linked_lists(linked_list_1, linked_list_2):
# merge two sorted linked lists into a new linked list
ll = LinkedList()
node1 = linked_list_1.head
node2 = linked_list_2.head
if node1 is None:
return linked_list_2.print_list()
if node2 is None:
return linked_list_1.print_list()
while node1 is not None and node2 is not None:
if node1.data == node2.data:
ll.add_at_head(node1)
ll.add_at_head(node2)
node1 = node1.next
node2 = node2.next
elif node1.data < node2.data:
ll.add_at_head(node1)
node1 = node1.next
else:
ll.add_at_head(node2)
node2 = node2.next
while node1 is not None:
ll.add_at_head(node1)
node1 = node1.next
while node2 is not None:
ll.add_at_head(node2)
node2 = node2.next
return ll.print_backward()
def create_linked_list(data):
ll = LinkedList()
for i in data:
node = Node(data=i)
ll.add_at_head(node)
return ll
linked_list_1 = create_linked_list([1,7, 8])
linked_list_2 = create_linked_list([5, 6, 11])
merge_linked_lists(linked_list_1, linked_list_2)
您需要更改 add_at_head 功能，一切都会正常。