时间戳

首页 > 解决方案 > 在 python 中合并 2 个链表不起作用。创建的第三个链接列表在执行后给了我一个 NULL 值/结果

python - 在 python 中合并 2 个链表不起作用。创建的第三个链接列表在执行后给了我一个 NULL 值/结果

问题描述

我目前坚持这个python练习，我有2个LinkedLists（linked_list_1，linked_list_2），我必须将它们合并到一个新的LinkedList中。我已经尝试过这段代码，但是当我需要它给我两个linkedLists中的数据时，它一直给我第三个LinkedList的空值。该函数被调用：merge_linked_lists(linked_list_1,linked_list_2)。这就是我的问题所在。如果有人可以提供帮助，我将不胜感激。

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):
    def merge(List_1, List_2):
        head_ptr = temp_ptr = Node() # head_ptr will be the head node of the output list 
    # temp_ptr will be used to insert nodes in the output list
    
    # Loop for merging two lists
    # Loop terminates when both lists reaches to its end
        while List_1 or List_2:
            # List_1 has not reached its end
            # and List_2 has either reached its end or its current node has data
            # greater than or equal to the data of List_1 node
            # than insert List_1 node in the ouput list
            if List_1 and (not List_2 or List_1.data <= List_2.data):
                temp_ptr.next = Node(List_1.data)
                List_1 = List_1.next
            # otherwise insert List_2 node in the ouput list
            else:
                temp_ptr.next = Node(List_2.data)
                List_2 = List_2.next
            # move temp_pointer to next position
            temp_ptr = temp_ptr.next
        # return output list
        return head_ptr.next
    merge(linked_list_1.head, linked_list_2.head)


# Test merge() function
LL1 = LinkedList()
LL1.add_at_head(Node(2))
LL1.add_at_head(Node(4))
LL1.add_at_head(Node(6))
LL1.add_at_head(Node(8))
LL2 = LinkedList()
LL2.add_at_head(Node(1))
LL2.add_at_head(Node(3))
LL2.add_at_head(Node(5))
LL2.add_at_head(Node(7))
# Merge Function
LL3 = LinkedList()
LL3.head = merge_linked_lists(LL1, LL2)
LL3.print_list()

编辑1：

对于任何想知道输出的人，我在我的 IDE（Pycharm）上尝试了这段代码，它给出了一个空的输出/结果。我还在 pythontutor 上尝试过（它在那里显示 i/o），我看到linked_list_1 和linked_list_2 没有改变，但第三个链表为空。同样在执行过程中，第三个链表能够将它们合并在一起，但它有一个额外的节点，即第一个节点（头），并且它没有 NONE 作为数据。

编辑2：

代码终于成功了！

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 sortList(self):  
            #Node current will point to head  
            current = self.head;  
            index = None;  
              
            if(self.head == None):  
                return;  
            else:  
                while(current != None):  
                    #Node index will point to node next to current  
                    index = current.next;  
                      
                    while(index != None):  
                        #If current node's data is greater than index's node data, swap the data between them  
                        if(current.data > index.data):  
                            temp = current.data;  
                            current.data = index.data;  
                            index.data = temp;  
                        index = index.next;  
                    current = current.next;
                
def merge_linked_lists(linked_list_1, linked_list_2):
    linked_list_1.sortList()
    linked_list_2.sortList()
    def merge(List_1, List_2):
        head_ptr = temp_ptr = Node() # head_ptr will be the head node of the output list 
    # temp_ptr will be used to insert nodes in the output list
    
    # Loop for merging two lists
    # Loop terminates when both lists reaches to its end
        while List_1 or List_2:
            # List_1 has not reached its end
            # and List_2 has either reached its end or its current node has data
            # greater than or equal to the data of List_1 node
            # than insert List_1 node in the ouput list
            if List_1 and (not List_2 or List_2.data >= List_1.data):
                temp_ptr.next = Node(List_1.data)
                List_1 = List_1.next
            # otherwise insert List_2 node in the ouput list
            else:
                temp_ptr.next = Node(List_2.data)
                List_2 = List_2.next
            # move temp_pointer to next position
            temp_ptr = temp_ptr.next
        # return output list
        return head_ptr.next
    return merge(linked_list_1.head, linked_list_2.head)


# Test merge() function
LL1 = LinkedList()
LL1.add_at_head(Node(2))
LL1.add_at_head(Node(4))
LL1.add_at_head(Node(6))
LL1.add_at_head(Node(8))
LL2 = LinkedList()
LL2.add_at_head(Node(1))
LL2.add_at_head(Node(3))
LL2.add_at_head(Node(5))
LL2.add_at_head(Node(7))
# Merge Function
LL3 = LinkedList()
LL3.head = merge_linked_lists(LL1, LL2)
LL3.print_list()

Ps：我还制作了另一个也有效的代码。

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 sortList(self):
        # Node current will point to head
        current = self.head;
        index = None;

        if (self.head == None):
            return;
        else:
            while (current != None):
                # Node index will point to node next to current
                index = current.next;

                while (index != None):
                    # If current node's data is greater than index's node data, swap the data between them
                    if (current.data < index.data):
                        temp = current.data;
                        current.data = index.data;
                        index.data = temp;
                    index = index.next;
                current = current.next;

    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):
    linked_list_1.sortList()
    linked_list_2.sortList()
    LL3 = LinkedList()
    node = linked_list_2.head
    node1 = linked_list_1.head
    if node is None and node1 is None:
        return LL3
    while True:
        if node1 is None:
            LL3.add_at_head(Node(node.data))
            node = node.next
            if node is None:
                return LL3
            else:
                continue
        if node is None:
            LL3.add_at_head(Node(node1.data))
            node1 = node1.next
            if node1 is None:
                return LL3
            else:
                continue
        if node.data > node1.data:
            LL3.add_at_head(Node(node.data))
            node = node.next
        if node1.data > node.data:
            LL3.add_at_head(Node(node1.data))
            node1 = node1.next
    return LL3
# Test merge() function
# Linked List with even numbers
LL1 = LinkedList()
LL1.add_at_head(Node(2))
LL1.add_at_head(Node(4))
LL1.add_at_head(Node(6))
LL1.add_at_head(Node(8))
# Linked List with odd numbers
LL2 = LinkedList()
LL2.add_at_head(Node(1))
LL2.add_at_head(Node(3))
LL2.add_at_head(Node(5))
LL2.add_at_head(Node(7))
# Merge Function
LL3 = LinkedList()
LL3 = merge_linked_lists(LL1, LL2)
LL3.print_list()

标签： pythonlinked-list

解决方案

您的merge函数没有返回语句：

改变：

merge(linked_list_1.head, linked_list_2.head)

到：

return merge(linked_list_1.head, linked_list_2.head)

另一个问题是您的两个输入列表的排序顺序是降序的，而您的合并函数假定它们是升序排序的。因此，您的合并列表未排序。

因此，要么将您的列表初始化为按顺序升序（记住您以相反的顺序插入值），要么在合并函数中更改<=为。>=

推荐阅读