educative.io

Educative

How to merge two sorted double link

HI

I have a question about second solution in this problem " Convert Binary Tree to Doubly Linked List".

The way which fused two sorted double link confused me.

def concatenate_lists(head1, head2):

  if head1 is None:

    return head2

  if head2 is None:

    return head1

  # use left for previous.

  # use right for next.

  tail1 = head1.left

  tail2 = head2.left

  tail1.right = head2

  head2.left = tail1

  head1.left = tail2

  tail2.right = head1

  return head1

Could you help me explain that why

head1.left = tail2
tail2.right = head1

Thanks