Попытка реализации сортировки слиянием связанного списка с помощью Python приводит к бесконечному циклу ⇐ Python

[Anonymous]

Контекст
Я реализовал решение для сортировки LinkedList с помощью Python (на сайте leetcode.com).
Решение представляет собой подход сортировки слиянием снизу вверх (разделяй и властвуй). .
Приведенный ниже код неполон, в нем отсутствует реализация метода merge(), который возьмет список заданного размера и объединит его, учитывая, что две половины списка уже отсортированы, т.е. возьмут половину и вставьте его где-нибудь в другую половину.
Я столкнулся с проблемой при тестировании других частей реализации.

Код: Выделить всё

sortList()

и merge_list_of_size()
Идея состоит в том, что sortList() начнет с рассмотрения всех подсписков размера 2 и их сортировки, вызывая merge_list_of_size() с list_size = 2.
SortList() продолжится, удвоив list_size, list_size = 4 и снова используйте merge_list_of_size() для сортировки всех списков этого размера.
Размер списка будет увеличиваться снова и снова, пока list_size не станет слишком большим для продолжения.
< pre class="lang-py Prettyprint-override">

Код: Выделить всё

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
N = 1
while N < 100:
N *= 2
print(N)
has_next_merge = self.merge_list_of_size(head, N)
if not has_next_merge:
print('has_next_merge', has_next_merge)
break
return head

def merge_list_of_size(self, head, list_size):
while head:
print('--', head)
next_merge = self.merge(head, list_size)
if not next_merge:
return False

i = list_size
while head and i > 0:
head = head.next
i -= 1
return True

def merge(self, head, list_size):
mid_i = list_size // 2
print(mid_i)
mid = head
while mid.next and mid_i > 1:
mid = mid.next
mid_i -= 1
print('----', mid)
if mid.next is None:
return False
else:
# merge
print('merging')
return True

Проблема с бесконечным циклом
При запуске приведенного выше кода с вводом этого связанного списка: [4,2,1,3]< /code>.
Обратите внимание на while в sortList().
Цикл прерывается, если:

• Код: Выделить всё

  merge_list_of_size()

  возвращает значение False
• N = >= 100

Это журнал вывод:

Код: Выделить всё

2
-- ListNode{val: 4, next: ListNode{val: 2, next: ListNode{val: 1, next: ListNode{val: 3, next: None}}}}
1
---- ListNode{val: 4, next: ListNode{val: 2, next: ListNode{val: 1, next: ListNode{val: 3, next: None}}}}
merging
-- ListNode{val: 1, next: ListNode{val: 3, next: None}}
1
---- ListNode{val: 1, next: ListNode{val: 3, next: None}}
merging
4
-- ListNode{val: 4, next: ListNode{val: 2, next: ListNode{val: 1, next: ListNode{val: 3, next: None}}}}
2
---- ListNode{val: 2, next: ListNode{val: 1, next: ListNode{val: 3, next: None}}}
merging
8
-- ListNode{val: 4, next: ListNode{val: 2, next: ListNode{val: 1, next: ListNode{val: 3, next: None}}}}
4
---- ListNode{val: 3, next: None}
has_next_merge False

• Бесконечный цикл отсутствует
• Программа завершает работу, как и ожидалось, когда merge_list_of_size() возвращает False для N = 8.

Если я теперь изменю while с while N < 100:< /code> to while True:, по какой-то неизвестной мне причине цикл невозможно разорвать. И вот что я получаю в журнале:

Код: Выделить всё

2
4
8
16
32
64
128
256
512
1024
2048
4096
8192
16384
32768
65536
131072
262144
524288
1048576
2097152
4194304
8388608
16777216
33554432
67108864
134217728
268435456
536870912
1073741824
2147483648
4294967296
8589934592
17179869184
34359738368
68719476736
137438953472
274877906944
549755813888
1099511627776
2199023255552
.
.
.

Не знаю, чего мне здесь не хватает. Буду признателен за любые подсказки. Спасибо.
Вот ссылка на проблему с лит-кодом.

Подробнее здесь: https://stackoverflow.com/questions/791 ... n-infinite