我不明白这些条件的必要性。 linked_list 如何以及何时可以成为 None？
I don't understand the need of these conditions. How and when can a linked_list be None?
(拆分函数中)
我 运行 它没有这些条件，它的工作原理与它们一样。
当我们到达单节点链表时，merge_sort函数的停止条件应该正好return相同的单节点链表返回，其余的可以继续下去。
我在教程中看到了这一点，这被解释为“当具有单个节点的 linked_list 通过拆分传递时，linked_list 可以是 none”
任何帮助将不胜感激
if linked_list == None or linked_list.head == None:
left_half = linked_list
right_half = None
这是整个程序
from linked_list import LinkedList
def merge_sort(linked_list):
"""
Sorts a linked list in ascending order
- Recursively divide the linked list into sublists containing a single node
- Repeatedly merge the sublists to produce sorted sublists until one remains
Returns a sorted linked list
Takes O(n log n) time
Takes O(n) space
"""
if linked_list.size() == 1 or linked_list.head is None:
return linked_list
left_half , right_half = split(linked_list)
left = merge_sort(left_half)
right = merge_sort(right_half)
return merge(left,right)
def split(linked_list):
"""
Divide the unsorted list at midpoint into sublists
Takes O(log n) time
"""
# linked_list can be none when a linked_list having a single node is passed through split
if linked_list == None or linked_list.head == None:
left_half = linked_list
right_half = None
return left_half,right_half
else:
size = linked_list.size()
mid = size//2
mid_node = linked_list.node_at_index(mid-1)
left_half = linked_list
right_half =LinkedList()
right_half.head = mid_node.next_node
mid_node.next_node = None
return left_half,right_half
def merge(left,right):
"""
Create a new list that contains the node from left and right
"""
merged = LinkedList()
#fake head to avoid guessing if there is a head in our new linked_list or not
merged.add(0)
current = merged.head
left_head = left.head
right_head = right.head
#iterate over left and right until we reach the tail node of both
while left_head or right_head:
#if the left_head is None, means we're past the tail node
# Add the tail node from right to the merged linked list
if left_head is None:
current.next_node = right_head
right_head = right_head.next_node
elif right_head is None:
# Add the tail node from left to the merged linked list
#if the right_head is None, means we're past the tail node
current.next_node = left_head
left_head = left_head.next_node
else:
#not at either tail node
#Obtain node data to perform comparison
left_data = left_head.data
right_data = right_head.data
if left_data < right_data:
current.next_node = left_head
left_head= left_head.next_node
else:
current.next_node = right_head
right_head = right_head.next_node
current= current.next_node
#discarding the fake head
head = merged.head.next_node
merged.head = head
return merged
这是我从中导入的 LinkedList 程序
class Node:
"""
An object for creating a Node
"""
def __init__(self,data,next_node=None):
self.data = data
self.next_node = next_node
def __repr__(self):
return "<Node: %s>"%self.data
class LinkedList:
"""
A (linear data structure)list to maintain the nodes created
The list refers to the first node as head and each node refers to the next node in the list
"""
def __init__(self):
self.head = None #an empty LinkedList
def is_empty(self):
return self.head is None
def size(self):
"""
if current is none, while loop doesn't run, size return 0
self.head = current, then we increase count and make current = self.next_node,
when next_node becomes none, which means current becomes 0, it is past the tail, in that case while loop breaks
"""
current = self.head
count = 0
while current:
count += 1
current = current.next_node
return count
def add(self,data):
"""
prepends the new date to the LinkedList
"""
new_node = Node(data)
new_node.next_node = self.head
self.head = new_node
def search(self,key):
"""
Searches the data by trasversing through the list. If not found, it returns None
"""
current = self.head
while current:
if current.data == key:
return current.data
current = current.next_node
return None
def insert(self,data,index):
"""
Inserts the data at a particular index by trasversing through the LinkedList.
Inserting is efficient as nothin needs to be shifted but finding and going to the index
makes it O(n)
"""
if index == 0:
self.add(data)
if index > 0:
new = Node(data)
pos = index
current = self.head
while pos > 1:
current = current.next_node
pos -= 1
prev_node = current
next_node = current.next_node
prev_node.next_node = new
new.next_node = next_node
def remove(self,key):
"""
Removes the first element matching the key in the LinkedList
returns None if the list is empty or if the key is not in the list
"""
current = self.head
prev = None
found = False
while current and not found:
if current.data == key and current is self.head: #if the key is at the head
found = True
self.head = current.next_node
elif current.data == key:
found = True
prev.next_node = current.next_node
else:
prev = current
current = current.next_node
return current
def remove_at_index(self,index):
current = self.head
pos = index
while pos > 0:
current = current.next_node
pos -= 1
self.remove(current.data)
def node_at_index(self,index):
"""
Returning the node at index by counting the number of times we used next_node on current.
if it becomes equal to the index, we return the current
"""
if index == 0:
return self.head
else:
current = self.head
pos = 0
while pos < index:
current = current.next_node
pos += 1
return current
def __repr__(self):
"""
returns a string representation of the list
"""
current = self.head
ls = []
while current:
if current is self.head:
ls.append('[Head: %s]'%current.data)
elif current.next_node is None:
ls.append('[Tail: %s]'%current.data)
else:
ls.append('[%s]'%current.data)
current = current.next_node
return '->'.join(ls)
如有愚蠢的错误，请原谅，我只是一个初学者。
你是对的，你不需要 split(linkedlist) 函数中的那些条件，因为你正在 merge_sort(linkedlist) 函数中检查边缘情况。
我想你提到的教程包含了它两次，使 split(linkedlist) 作为一个独立的函数工作，即它可以在任何 LinkedList 上工作。
(In split function) I ran it without these conditions, and it worked just as same as with them
如果您要删除此代码：
if linked_list == None or linked_list.head == None:
left_half = linked_list
right_half = None
return left_half,right_half
else:
...只保留 else 块中的代码，然后它将适用于所有链表（也适用于只有一个节点的列表，如您正确所述），except 当其大小为 0:
lst = LinkedList()
left, right = split(lst) # AttributeError: 'NoneType' object has no attribute 'next_node'
此测试代码将失败，因为 mid_node = linked_list.node_at_index(mid-1) 将分配 None，因为索引 -1 处没有节点。当代码继续计算 mid_node.next.
时发生异常
但是，我同意用 None 参数调用 split 毫无意义。然而，代码通过这样做实现了这一点：
if linked_list == None or linked_list.head == None:
left_half = linked_list
right_half = None # <--- here
这很糟糕！如果我们用一个没有节点的链表调用 split，那么我们会得到 left_half（空列表）和 right_half（None）不同的值！绝对没有充分的理由为什么要这样做。 split应该总是return一对链表实例。所以代码应该更正为：
if linked_list.head == None:
left_half = linked_list
right_half = LinkedList() # <-- create an empty list
现在他们的评论不再正确：split 不能 return 一个 None 列表。因此，使用 returned 值对 split 的任何后续调用都将获得一个链表实例（而不是 None）。 None 列表的整个概念不应该存在。一个空列表应该仍然是 LinkedList.
的一个实例
其他备注
split 改变它作为参数获取的列表。事实上，在调用之后，input 列表与 returned 的 left 列表相同。这会误导不知情的来电者。评论中没有提到这一点。如果函数被调用 splitOffRightHalf 并且函数只是 return right_half 会更好。然后调用者会从名称中知道原始列表将被截断到它的左半部分。
此外，为了避免任何关于 None 参数的讨论（实际上这个函数永远不应该得到），这个函数最好是 方法 LinkedList class，并且只得到 self 作为参数。这样很自然地在现有链表实例上调用它，并且不需要检查 None。
我没有检查其余代码，但我无意中发现了 split 函数的注释：
# Takes O(log n) time
这不是真的。 split 取决于 node_at_index 这需要 O(n) 时间。这个错误的注释大大降低了我对这段代码的信任。
(拆分函数中) 我 运行 它没有这些条件，它的工作原理与它们一样。 当我们到达单节点链表时，merge_sort函数的停止条件应该正好return相同的单节点链表返回，其余的可以继续下去。 我在教程中看到了这一点，这被解释为“当具有单个节点的 linked_list 通过拆分传递时，linked_list 可以是 none” 任何帮助将不胜感激
if linked_list == None or linked_list.head == None:
left_half = linked_list
right_half = None
这是整个程序
from linked_list import LinkedList
def merge_sort(linked_list):
"""
Sorts a linked list in ascending order
- Recursively divide the linked list into sublists containing a single node
- Repeatedly merge the sublists to produce sorted sublists until one remains
Returns a sorted linked list
Takes O(n log n) time
Takes O(n) space
"""
if linked_list.size() == 1 or linked_list.head is None:
return linked_list
left_half , right_half = split(linked_list)
left = merge_sort(left_half)
right = merge_sort(right_half)
return merge(left,right)
def split(linked_list):
"""
Divide the unsorted list at midpoint into sublists
Takes O(log n) time
"""
# linked_list can be none when a linked_list having a single node is passed through split
if linked_list == None or linked_list.head == None:
left_half = linked_list
right_half = None
return left_half,right_half
else:
size = linked_list.size()
mid = size//2
mid_node = linked_list.node_at_index(mid-1)
left_half = linked_list
right_half =LinkedList()
right_half.head = mid_node.next_node
mid_node.next_node = None
return left_half,right_half
def merge(left,right):
"""
Create a new list that contains the node from left and right
"""
merged = LinkedList()
#fake head to avoid guessing if there is a head in our new linked_list or not
merged.add(0)
current = merged.head
left_head = left.head
right_head = right.head
#iterate over left and right until we reach the tail node of both
while left_head or right_head:
#if the left_head is None, means we're past the tail node
# Add the tail node from right to the merged linked list
if left_head is None:
current.next_node = right_head
right_head = right_head.next_node
elif right_head is None:
# Add the tail node from left to the merged linked list
#if the right_head is None, means we're past the tail node
current.next_node = left_head
left_head = left_head.next_node
else:
#not at either tail node
#Obtain node data to perform comparison
left_data = left_head.data
right_data = right_head.data
if left_data < right_data:
current.next_node = left_head
left_head= left_head.next_node
else:
current.next_node = right_head
right_head = right_head.next_node
current= current.next_node
#discarding the fake head
head = merged.head.next_node
merged.head = head
return merged
这是我从中导入的 LinkedList 程序
class Node:
"""
An object for creating a Node
"""
def __init__(self,data,next_node=None):
self.data = data
self.next_node = next_node
def __repr__(self):
return "<Node: %s>"%self.data
class LinkedList:
"""
A (linear data structure)list to maintain the nodes created
The list refers to the first node as head and each node refers to the next node in the list
"""
def __init__(self):
self.head = None #an empty LinkedList
def is_empty(self):
return self.head is None
def size(self):
"""
if current is none, while loop doesn't run, size return 0
self.head = current, then we increase count and make current = self.next_node,
when next_node becomes none, which means current becomes 0, it is past the tail, in that case while loop breaks
"""
current = self.head
count = 0
while current:
count += 1
current = current.next_node
return count
def add(self,data):
"""
prepends the new date to the LinkedList
"""
new_node = Node(data)
new_node.next_node = self.head
self.head = new_node
def search(self,key):
"""
Searches the data by trasversing through the list. If not found, it returns None
"""
current = self.head
while current:
if current.data == key:
return current.data
current = current.next_node
return None
def insert(self,data,index):
"""
Inserts the data at a particular index by trasversing through the LinkedList.
Inserting is efficient as nothin needs to be shifted but finding and going to the index
makes it O(n)
"""
if index == 0:
self.add(data)
if index > 0:
new = Node(data)
pos = index
current = self.head
while pos > 1:
current = current.next_node
pos -= 1
prev_node = current
next_node = current.next_node
prev_node.next_node = new
new.next_node = next_node
def remove(self,key):
"""
Removes the first element matching the key in the LinkedList
returns None if the list is empty or if the key is not in the list
"""
current = self.head
prev = None
found = False
while current and not found:
if current.data == key and current is self.head: #if the key is at the head
found = True
self.head = current.next_node
elif current.data == key:
found = True
prev.next_node = current.next_node
else:
prev = current
current = current.next_node
return current
def remove_at_index(self,index):
current = self.head
pos = index
while pos > 0:
current = current.next_node
pos -= 1
self.remove(current.data)
def node_at_index(self,index):
"""
Returning the node at index by counting the number of times we used next_node on current.
if it becomes equal to the index, we return the current
"""
if index == 0:
return self.head
else:
current = self.head
pos = 0
while pos < index:
current = current.next_node
pos += 1
return current
def __repr__(self):
"""
returns a string representation of the list
"""
current = self.head
ls = []
while current:
if current is self.head:
ls.append('[Head: %s]'%current.data)
elif current.next_node is None:
ls.append('[Tail: %s]'%current.data)
else:
ls.append('[%s]'%current.data)
current = current.next_node
return '->'.join(ls)
如有愚蠢的错误，请原谅，我只是一个初学者。
你是对的，你不需要 split(linkedlist) 函数中的那些条件，因为你正在 merge_sort(linkedlist) 函数中检查边缘情况。
我想你提到的教程包含了它两次，使 split(linkedlist) 作为一个独立的函数工作，即它可以在任何 LinkedList 上工作。
(In split function) I ran it without these conditions, and it worked just as same as with them
如果您要删除此代码：
if linked_list == None or linked_list.head == None:
left_half = linked_list
right_half = None
return left_half,right_half
else:
...只保留 else 块中的代码，然后它将适用于所有链表（也适用于只有一个节点的列表，如您正确所述），except 当其大小为 0:
lst = LinkedList()
left, right = split(lst) # AttributeError: 'NoneType' object has no attribute 'next_node'
此测试代码将失败，因为 mid_node = linked_list.node_at_index(mid-1) 将分配 None，因为索引 -1 处没有节点。当代码继续计算 mid_node.next.
但是，我同意用 None 参数调用 split 毫无意义。然而，代码通过这样做实现了这一点：
if linked_list == None or linked_list.head == None:
left_half = linked_list
right_half = None # <--- here
这很糟糕！如果我们用一个没有节点的链表调用 split，那么我们会得到 left_half（空列表）和 right_half（None）不同的值！绝对没有充分的理由为什么要这样做。 split应该总是return一对链表实例。所以代码应该更正为：
if linked_list.head == None:
left_half = linked_list
right_half = LinkedList() # <-- create an empty list
现在他们的评论不再正确：split 不能 return 一个 None 列表。因此，使用 returned 值对 split 的任何后续调用都将获得一个链表实例（而不是 None）。 None 列表的整个概念不应该存在。一个空列表应该仍然是 LinkedList.
其他备注
split 改变它作为参数获取的列表。事实上，在调用之后，input 列表与 returned 的 left 列表相同。这会误导不知情的来电者。评论中没有提到这一点。如果函数被调用 splitOffRightHalf 并且函数只是 return right_half 会更好。然后调用者会从名称中知道原始列表将被截断到它的左半部分。
此外，为了避免任何关于 None 参数的讨论（实际上这个函数永远不应该得到），这个函数最好是 方法 LinkedList class，并且只得到 self 作为参数。这样很自然地在现有链表实例上调用它，并且不需要检查 None。
我没有检查其余代码，但我无意中发现了 split 函数的注释：
# Takes O(log n) time
这不是真的。 split 取决于 node_at_index 这需要 O(n) 时间。这个错误的注释大大降低了我对这段代码的信任。