I’m not understanding the need for this line of code after recursively processing the left and right subtrees… What exactly is the purpose for this?
It seems like a backtracking technique, but I am unable to wrap my head around it.
I’m not understanding the need for this line of code after recursively processing the left and right subtrees… What exactly is the purpose for this?
It seems like a backtracking technique, but I am unable to wrap my head around it.
The following line code is to have the left and right pointers to point to itself.
root.left = root.right = root
We have the root
point to itself before passing it to the concatenate_lists
function. Because inside the concate function we assign whatever’s in root.left
or root.right
to tail1
and tail2
and we don’t want tail1
and tail2
to be null as we have not made a check for it when we call on its left and right attributes. You can test it out by comment ing out the above line of code, you will get a compilation error (on python) that the None
object has no attribute right on either lines: tail1.right = head2
or tail2.right = head2
as tail1
/tail2
is null.
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
You can also declare an entirely new node and point root.right and root.left to it, and the code will work correctly. In short, this line is just there to make sure there are no null nodes in root.left
or root.right
when passing root
to the concatenate_lists
functions.