파이썬

Question

여기

하나의 연결리스트에 두 개의 정렬 된 연결리스트를 병합 내 코드입니다 :

def merge_lists(head1, head2): 
    if head1 is None and head2 is None: 
     return None 
    if head1 is None: 
     return head2 
    if head2 is None: 
     return head1 
    if head1.value < head2.value: 
     temp = head1 
    else: 
     temp = head2 
    while head1 != None and head2 != None: 
     if head1.value < head2.value: 
      temp.next = head1 
      head1 = head1.next 
     else: 
      temp.next = head2 
      head2 = head2.next 
    if head1 is None: 
     temp.next = head2 
    else: 
     temp.next = head1 
    return temp 
    pass 

여기에 하나 loop.can 무한에 stucked하는 문제는 문제가

무엇인지 말해 예는 :

assert [] == merge_lists([],[]) 
assert [1,2,3] == merge_lists([1,2,3], []) 
assert [1,2,3] == merge_lists([], [1,2,3]) 
assert [1,1,2,2,3,3,4,5] == merge_lists([1,2,3], [1,2,3,4,5]) 

Answer 1

현재 코드의 문제점은 그것의 부작용을 야기한다는 것이다 그 다음에 탐색 임시 노드의 다음 전 현재 노드의 노드. 이는 현재 임시 노드 이 현재 노드 인 일 때 문제가됩니다.

def merge_lists(head1, head2): 
    if head1 is None: 
     return head2 
    if head2 is None: 
     return head1 

    # create dummy node to avoid additional checks in loop 
    s = t = node() 
    while not (head1 is None or head2 is None): 
     if head1.value < head2.value: 
      # remember current low-node 
      c = head1 
      # follow ->next 
      head1 = head1.next 
     else: 
      # remember current low-node 
      c = head2 
      # follow ->next 
      head2 = head2.next 

     # only mutate the node AFTER we have followed ->next 
     t.next = c   
     # and make sure we also advance the temp 
     t = t.next 

    t.next = head1 or head2 

    # return tail of dummy node 
    return s.next 

Answer 2

재귀 알고리즘이 분류 연결리스트

def merge_lists(h1, h2): 
    if h1 is None: 
     return h2 
    if h2 is None: 
     return h1 

    if (h1.value < h2.value): 
     h1.next = merge_lists(h1.next, h2) 
     return h1 
    else: 
     h2.next = merge_lists(h2.next, h1) 
     return h2