三个月算法进阶--day10
目录
递归时若有参数是不断减少的列表，要注意递归到第二层停止
链表小心节点循环，不要ans.next = ans
头插
tmp.next = head
head = tmp
中间插（原地）
prev = head
prev = prev.next
...
prev.next = newNode.next(prev.next)
记录
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeKLists(self, lists):
if not lists:
return
new_lists = []
for i in lists:
if i:
new_lists.append(i)
if not new_lists:
return
if len(new_lists) == 1:
return new_lists[0]
elif len(new_lists) == 2:
alist = new_lists[0]
blist = new_lists[1]
ans = alist
while blist != None:
insert_value = blist.val
if insert_value <= ans.val:
ans = ListNode(insert_value, ans)
blist = blist.next
continue
prev = ans
while prev.next != None:
if insert_value <= prev.next.val:
prev.next = ListNode(insert_value, prev.next)
break
prev = prev.next
else:
prev.next = ListNode(insert_value)
blist = blist.next
return ans
else:
tail_list = new_lists.pop()
return self.mergeKLists([self.mergeKLists(new_lists), tail_list])