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

Question

我写了这样一个解决方案 merge two sorted list　合并两个已排序的链表并将其作为新列表返回。应该通过将前两个列表的节点拼接在一起来制作新列表。例子：Input: 1->2->4, 1->3->4Output: 1->1->2->3->4->4我的解决方案：# Definition for singly-linked list.class ListNode:    def __init__(self, x):        self.val = x        self.next = Noneclass 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应该确定应附加下一个节点的位置，因此

   l3 = head

您需要将给定 (l1或l2)列表之一的头部附加到l3，但您不需要。

在添加节点之后，您需要同时推进源列表的头指针 ( l1or l2) 和目标列表的尾指针 ( l3)：

    while l1 and l2:     #assert both exist

        if l2.val < l1.val:

            l3.next = l2 #append new node to the resulting list

            l2 = l2.next #and skip it in the source list 

        else:

            l3.next = l1

            l1 = l1.next     

        l3 = l3.next     #find the next to build

Answer 2

这是我的解决方案

class ListNode:

    def __init__(self, x):

        self.val = x

        self.next = None

    def insert(self,el):

        Node = self

        while Node:

            if Node.next==None:

                Node.next = ListNode(el)

                break

            else:

                Node =Node.next

    def prin(node):

        while node:

            if node.next:

                print(node.val,end='-> ')

            else:

                print(node.val)

            node = node.next

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

    """

    Plan:

    Compare l1 and l2 and merge the remainders

    """

    _node = None

    if l1.val<l2.val:

        _node = ListNode(l1.val)

        l1 =l1.next

    else:

        _node = ListNode(l2.val)

        l2=l2.next

    l3 = _node        

    while l1 and l2: #assert both exist

        if l2.val < l1.val:

            l3.insert(l2.val)

            l2 = l2.next

        else:

            l3.insert(l1.val)

            l1 = l1.next     

    while l1:

        l3.insert(l1.val)

        l1 =l1.next

    while l2:

        l3.insert(l2.val)

        l2 = l2.next

    return l3

node1= 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):

    first = ListNode(0)

    # 'here' is where we link in the nodes.

    here = first

    while l1 and l2:

        # Pick the next node from the inputs.

        # Note that this has the same effect as assigning

        # to 'first.next' on the first iteration, when 'first' and 'here'

        # refer to the same object.

        if l1.val < l2.val:

            here.next = l1

        else:

            here.next = l2

        # Move along to the last node we picked.

        here = here.next

    # Grab the rest.

    if l1:

        here.next = l1

    else:

        here.next = l2

    return first.next