Flattening a Linked List

algorithm
,
#1

The problem we are exploring is to flatten a singly linked list. The initial singly linked list (to be flattened) has nodes of the following type:

This is a companion discussion topic for the original entry at http://iq.opengenus.org/flattening-a-linked-list/
#2

can any one explain the time complexity? It sounds like o(n) as we are only traversing n nodes and each comparison seems to be a constant operations.

#3

Yes, I think the time complexity is O(n). The space complexity is O(n) as well, because we are creating 1 new node when we visit a particular node and at last we are visiting each node once.

I request author to look into this and also provide lucid explanation instead of only giving pseudocode and code (may be add visualization or something like that).

Thanks!