I’m learning datastructure while compiling this mergesort linkedlist . I got this error. I tried so much but didn’t work. Can any one tell me what’s wrong? please .
Traceback (most recent call last): File “C:Users**AppDataLocalProgramsPythonPython37merge_sort_ver_2.0 linked list.py”, line 122, in
sorted_list=merge_sort(lst)
File “C:Users**AppDataLocalProgramsPythonPython37merge_sort_ver_2.0 linked list.py”, line 75, in merge_sort
return merge(left,right)
File “C:Users**AppDataLocalProgramsPythonPython37merge_sort_ver_2.0 linked list.py”, line 94, in merge
left_head=left.head
AttributeError: ‘NoneType’ object has no attribute ‘head’
def merge_sort(ll): if ll.length()==1: return ll elif ll.head is None: return ll left_half,right_half=split(ll) left=merge_sort(left_half) right=merge_sort(right_half) return merge(left,right) def split(ll): if ll.head==None or ll==None: left_half=ll right_half=None return left_half,right_half else: size=ll.length() mid=size//2 mid_node=ll.nodeAt(mid-1) right_half=ll left_half=LinkedList() left_half.head=mid_node.next mid_node.next=None return left_half,right_half def merge(left,right): merged=LinkedList() merged.tailinsert(0) current=merged.head left_head=left.head right_head=right.head while left_head or right_head: if left_head is None: current.next=right_head right_head=right_head.next elif right_head is None: current.next=left_head left_head=left_head.next else: merged.head=head return merged.printlist() lst=LinkedList() lst.tailinsert(14) lst.tailinsert(46) lst.tailinsert(43) lst.tailinsert(27) sorted_list=merge_sort(lst) print(sorted_list)
Advertisement
Answer
thanks Jérômei for your tips i cleared the error
def merge_sort(ll): if ll.length()==1: return ll elif ll.head is None: return ll left_half,right_half=split(ll) left=merge_sort(left_half) right=merge_sort(right_half) return merge(left,right) def split(ll): if ll.head==None or ll==None: left_half=ll right_half=None return left_half,right_half else: size=ll.length() mid=size//2 mid_node=ll.nodeAt(mid-1) right_half=LinkedList() left_half=ll right_half.head=mid_node.next mid_node.next=None return left_half,right_half def merge(left,right): merged=LinkedList() merged.tailinsert(0) current=merged.head left_head=left.head right_head=right.head while left_head and right_head : left_data=left_head.data right_data=right_head.data if left_data < right_data: current.next=left_head left_head=left_head.next elif right_data <left_data: current.next=right_head right_head=right_head.next current=current.next while right_head is not None : current.next=right_head right_head=right_head.next current=current.next while left_head is not None : current.next=left_head left_head=left_head.next current=current.next current=current.next head=merged.head.next merged.head=head print("merged 1:") merged.printlist() return merged lst=LinkedList() lst.tailinsert(14) lst.tailinsert(46) lst.tailinsert(43) lst.tailinsert(27) merge_sort(lst) **output: merged 1: 14 46 merged 1: 27 43 merged 1: 14 27 43 46**