python - 我不明白这些条件的必要性。链接列表如何以及何时可以为无？

Question

（在拆分功能中）我在没有这些条件的情况下运行它，它的工作方式与它们相同。当我们到达单节点链表时，merge_sort 函数的停止条件应该只是返回相同的单节点链表，然后可以继续。我在教程中看到了这一点，这被解释为“当具有单个节点的链接列表通过拆分传递时，链接列表可以是无”任何帮助将不胜感激

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)

如果有任何愚蠢的错误，请原谅，我只是一个初学者。

标签： pythonlinked-listmergesort

Answer 1

你是对的，你不需要函数中的这些条件，split(linkedlist)因为你正在检查merge_sort(linkedlist)函数中的边缘情况。我想您提到的教程包含两次以使其split(linkedlist)作为独立函数工作，即它可以在任何 LinkedList 上工作。