- #[LeetCode] Merge k Sorted Lists 合并 k 个有序链表 (升序)
- import numpy as np
- import time
- class Node(object):
- def __init__(self,n,next_node=None):
- self.data=n
- self.next=next_node
- class linklist(object):
- def __init__(self):
- self.head=None
- def init(self,data):
- assert type(data)==list,type(data)
- self.head=Node(data[0],None)
- p=self.head
- for i in data[1:]:
- node=Node(i)
- p.next=node
- p=p.next
- def show(self):
- l=[]
- p=self.head
- while p:
- l.append(str(p.data))
- p=p.next
- print('->'.join(l))
- def hebing(link1,link2):
- p1,p2=link1.head,link2.head
- if p1.data>p2.data:
- return hebing(link2,link1)
- while p2:
- if not p1.next and p2.next:
- p1.next=p2
- return link1
- if p1.data <p2.data and p1.next.data>p2.data:
- px=p1.next
- py=p2.next
- p1.next=p2
- p2.next=px
- p2=py
- p1=px
- elif p1.next.data<p2.data:
- p1=p1.next
- return link1
- def fenzu(group):
- n=len(group)
- if n==1:
- return group[0]
- elif n==2:
- return hebing(group[0],group[1])
- else:
- return hebing(fenzu(group[:n//2]),fenzu(group[n//2:]))
- l1,l2,l3=[1,3,5,9],[0,2,4,6,8,10],[3.1,5.5,15,46]
- link1,link2,link3=linklist(),linklist(),linklist()
- link1.init(l1)
- link2.init(l2)
- link3.init(l3)
- fenzu([link1,link2,link3]).show()
来源: http://www.bubuko.com/infodetail-2701539.html