在 Python 中按升序合并两个排序的链表：单链表指针更新问题

Question

# Definition for singly-linked list.
class ListNode:
     def __init__(self, x):
         self.val = x
         self.next = None

a = ListNode(5)
b = ListNode(10)
c = ListNode(20)


e = ListNode(0)
f = ListNode(5)
g = ListNode(21)
h = ListNode(30)


a.next = b
b.next = c

e.next = f
f.next = g
g.next = h

所以我有两个头为 a 和 e

的单向链表

我想按它们值的升序合并。现在，我想合并它们，遍历两个链表，比较值，直到其中一个链表达到 None（其中一个链表比另一个短，因此一个将达到 None 在另一个之前）

class Solution:
    def mergeTwoLists(self, l1, l2):

        tempNode = ListNode(0)
        returnNode = tempNode

        while (l1.next != None) and (l2.next != None):



            if l1.val < l2.val:

                print("l1.val < l2.val", l1.val, l2.val)
                tempNode.next = l1

                tempNode = tempNode.next
                l1 = l1.next

            elif l1.val == l2.val:

                print("l1.val == l2.val", l1.val, l2.val)

                #If both the values are equal, assign l1's value first
                #then make l2's value follow l1's value using tempNode 

                tempNode.next = l1 
                tempNode = tempNode.next #Because of the previous statement, after execution of this statement, I'm assuming tempNode.val is now l1.val and tempNode.next = l1.next

                #tempNode.next is supposed to be equal to l1.next, instead assign it to l2
                tempNode.next = l2
                tempNode = tempNode.next #Because of the previous statement, after execution of this statement, I'm assuming tempNode.val is now l2.val and tempNode.next = l2.next

                #Increment both l1 and l2
                l1 = l1.next
                l2 = l2.next


            else:
                print("l1.val > l2.val", l1.val, l2.val)
                tempNode.next = l2

                tempNode = tempNode.next
                l2 = l2.next

sol = Solution()
sol.mergeTwoLists(a, e)

所以这就是我理想中希望发生的事情，但显然没有发生，正如您在打印报表时所看到的那样！

l1.val = 5 > l2.val = 0

增加或向前移动 l2!

l1.val = 5 即 == l2.val == 5

它们是相等的，所以将 l1 移到下一个并且将 l2 移到下一个

现在，l1.val 应该是 10 而 l2.val 应该是 21，但是 l1.val 被打印为 5 并且 l2.val 被打印为 21 并卡在某个无限循环中..

为什么 l1.val 停留在 5 而不是更新为 10 并且为什么它停留在这个无限循环中而不是其中一个根据我的 while声明？

Answer 1

问题出在以下代码片段

tempNode.next = l1 
tempNode = tempNode.next 
tempNode.next = l2
tempNode = tempNode.next
l1 = l1.next
l2 = l2.next

只需将其更改为以下内容，您的代码即可运行

tempNode.next = l1 
tempNode = tempNode.next
l1 = l1.next 
tempNode.next = l2
tempNode = tempNode.next
l2 = l2.next

您的方法存在问题，当您执行 tempNode.next = l2 时，您正在修改 l1 指向的实际 ListNode，这使您陷入无限循环

Answer 2

您需要将 l1 和 l2 的值分配给 tempNode.val 而不是将 l1 和 l2 节点本身分配给 tempNode的下一个节点。如果另一个列表为空，您还需要将 l1 或 l2 的剩余值添加到 tempNode。

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x=None):
        self.val = x
        self.next = None

a = ListNode(5)
b = ListNode(10)
c = ListNode(20)


e = ListNode(0)
f = ListNode(5)
g = ListNode(21)
h = ListNode(30)


a.next = b
b.next = c

e.next = f
f.next = g
g.next = h

class Solution:
    def mergeTwoLists(self, l1, l2):

        returnNode = tempNode = ListNode()

        while l1 or l2:
            if not l1:
                print('l1 is empty; adding value from l2:', l2.val)
                tempNode.val = l2.val
                tempNode.next = ListNode()
                tempNode = tempNode.next
                l2 = l2.next
            elif not l2:
                print('l2 is empty; adding value from l1:', l1.val)
                tempNode.val = l1.val
                tempNode.next = ListNode()
                tempNode = tempNode.next
                l1 = l1.next
            elif l1.val < l2.val:

                print("l1.val < l2.val", l1.val, l2.val)
                tempNode.val = l1.val

                tempNode.next = ListNode()
                tempNode = tempNode.next
                l1 = l1.next

            elif l1.val == l2.val:

                print("l1.val == l2.val", l1.val, l2.val)

                #If both the values are equal, assign l1's value first
                #then make l2's value follow l1's value using tempNode

                tempNode.val = l1.val
                tempNode.next = ListNode() #Because of the previous statement, after execution of this statement, I'm assuming tempNode.val is now l1.val and tempNode.next = l1.next
                tempNode = tempNode.next

                #tempNode.next is supposed to be equal to l1.next, instead assign it to l2
                tempNode.val = l2.val
                tempNode.next = ListNode() #Because of the previous statement, after execution of this statement, I'm assuming tempNode.val is now l2.val and tempNode.next = l2.next
                tempNode = tempNode.next

                #Increment both l1 and l2
                l1 = l1.next
                l2 = l2.next


            else:
                print("l1.val > l2.val", l1.val, l2.val)
                tempNode.val = l2.val

                tempNode.next = ListNode()
                tempNode = tempNode.next
                l2 = l2.next
        return returnNode

sol = Solution()
node = sol.mergeTwoLists(a, e)
while node and node.val is not None:
    print(node.val)
    node = node.next

这输出：

l1.val > l2.val 5 0
l1.val == l2.val 5 5
l1.val < l2.val 10 21
l1.val < l2.val 20 21
l1 is empty; adding value from l2: 21
l1 is empty; adding value from l2: 30
0
5
5
10
20
21
30

在 Python 中按升序合并两个排序的链表：单链表指针更新问题

Merge two sorted Linked Lists in ascending order in Python: Issue with Singly Linked List pointer update

python

pointers

linked-list

python-3.x

singly-linked-list