Объединение двух отсортированных связанных списков в возрастающем порядке в 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

Вам необходимо присвоить 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

Answer 2

Проблема в следующем фрагменте кода

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, вы изменяете фактическое ListNode, на которое указывает l1, что застревает в бесконечном цикле