合并两个链接的排序列表但得到意想不到的答案

Question

我写了这样一个解决方案 merge two sorted list

　合并两个已排序的链表并将其作为新列表返回。应该通过将前两个列表的节点拼接在一起来制作新列表。

例子：

Input: 1->2->4, 1->3->4

Output: 1->1->2->3->4->4

我的解决方案：

# Definition for singly-linked list.

class ListNode:

    def __init__(self, x):

        self.val = x

        self.next = None

class Solution3:

    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:

        """

        Plan:

        Compare l1 and l2 and merge the remainders

        """

        head = ListNode(0) #create head to hold 

        l3 = ListNode(0)        

        head.next = l3 

        while l1 and l2: #assert both exist

            if l2.val < l1.val:

                l3 = l2 #build l3's node

                l2 = l2.next #this is i++ 

            else:

                l3 = l1

                l1 = l1.next     

            l3 = l3.next #find the next to build

        if l1:

            l3 = l1 

        if l2:

            l3 = l2

        return head.next

但得到错误的答案

输入

[1,2,4] [1,3,4]

输出

[0]

预期的

[1,1,2,3,4,4]

我检查过但找不到我的逻辑有任何问题。

你能帮我一下吗？

Answer 1

您l3应该确定应附加下一个节点的位置，因此&nbsp; &nbsp;l3 = head您需要将给定 (l1或l2)列表之一的头部附加到l3，但您不需要。在添加节点之后，您需要同时推进源列表的头指针 ( l1or l2) 和目标列表的尾指针 ( l3)：&nbsp; &nbsp; while l1 and l2:&nbsp; &nbsp; &nbsp;#assert both exist&nbsp; &nbsp; &nbsp; &nbsp; if l2.val < l1.val:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; l3.next = l2 #append new node to the resulting list&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; l2 = l2.next #and skip it in the source list&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; l3.next = l1&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; l1 = l1.next&nbsp; &nbsp; &nbsp;&nbsp; &nbsp; &nbsp; &nbsp; l3 = l3.next&nbsp; &nbsp; &nbsp;#find the next to build

Answer 2

这是我的解决方案class ListNode:&nbsp; &nbsp; def __init__(self, x):&nbsp; &nbsp; &nbsp; &nbsp; self.val = x&nbsp; &nbsp; &nbsp; &nbsp; self.next = None&nbsp; &nbsp; def insert(self,el):&nbsp; &nbsp; &nbsp; &nbsp; Node = self&nbsp; &nbsp; &nbsp; &nbsp; while Node:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if Node.next==None:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Node.next = ListNode(el)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Node =Node.next&nbsp; &nbsp; def prin(node):&nbsp; &nbsp; &nbsp; &nbsp; while node:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if node.next:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; print(node.val,end='-> ')&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; print(node.val)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; node = node.nextdef mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:&nbsp; &nbsp; """&nbsp; &nbsp; Plan:&nbsp; &nbsp; Compare l1 and l2 and merge the remainders&nbsp; &nbsp; """&nbsp; &nbsp; _node = None&nbsp; &nbsp; if l1.val<l2.val:&nbsp; &nbsp; &nbsp; &nbsp; _node = ListNode(l1.val)&nbsp; &nbsp; &nbsp; &nbsp; l1 =l1.next&nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; _node = ListNode(l2.val)&nbsp; &nbsp; &nbsp; &nbsp; l2=l2.next&nbsp; &nbsp; l3 = _node&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp; &nbsp; while l1 and l2: #assert both exist&nbsp; &nbsp; &nbsp; &nbsp; if l2.val < l1.val:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; l3.insert(l2.val)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; l2 = l2.next&nbsp; &nbsp; &nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; l3.insert(l1.val)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; l1 = l1.next&nbsp; &nbsp; &nbsp;&nbsp; &nbsp; while l1:&nbsp; &nbsp; &nbsp; &nbsp; l3.insert(l1.val)&nbsp; &nbsp; &nbsp; &nbsp; l1 =l1.next&nbsp; &nbsp; while l2:&nbsp; &nbsp; &nbsp; &nbsp; l3.insert(l2.val)&nbsp; &nbsp; &nbsp; &nbsp; l2 = l2.next&nbsp; &nbsp; return l3node1= ListNode(1)node1.insert(2)node1.insert(4)node2 = ListNode(1)node2.insert(3)node2.insert(4)solved_list = mergeTwoLists(node1,node2)solved_list.prin()

Answer 3

你永远改变表结构（有任何不分配next在循环S），你只是移动l1，l2以及l3沿输入列表。然后您返回head.next，它仍然是您首先分配给它的节点。由于您使用哨兵节点的方法使代码比不使用更简单，因此我将其保留在此处：def merge(l1, l2):&nbsp; &nbsp; first = ListNode(0)&nbsp; &nbsp; # 'here' is where we link in the nodes.&nbsp; &nbsp; here = first&nbsp; &nbsp; while l1 and l2:&nbsp; &nbsp; &nbsp; &nbsp; # Pick the next node from the inputs.&nbsp; &nbsp; &nbsp; &nbsp; # Note that this has the same effect as assigning&nbsp; &nbsp; &nbsp; &nbsp; # to 'first.next' on the first iteration, when 'first' and 'here'&nbsp; &nbsp; &nbsp; &nbsp; # refer to the same object.&nbsp; &nbsp; &nbsp; &nbsp; if l1.val < l2.val:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; here.next = l1&nbsp; &nbsp; &nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; here.next = l2&nbsp; &nbsp; &nbsp; &nbsp; # Move along to the last node we picked.&nbsp; &nbsp; &nbsp; &nbsp; here = here.next&nbsp; &nbsp; # Grab the rest.&nbsp; &nbsp; if l1:&nbsp; &nbsp; &nbsp; &nbsp; here.next = l1&nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; here.next = l2&nbsp; &nbsp; return first.next