Hello.

Quite often, during interviews or in test tasks (for internship, for example), a question is asked about simply linked lists .

For example, they give a task in which it is necessary to expand a simply connected list in O (n) time. So, how to do it? Can I just override the links? Those. do for 1 iteration so that not A-> B , but A <-B ?

Can you please give an example? Thank you in advance

2 answers 2

The first link is from Google.

void reverse(OneWayList list){ OneWayList.Node node = list.head; OneWayList.Node previous = null; while(node != null){ //next item OneWayList.Node tmp = node.next; //swap items node.next = previous; previous = node; list.head = node; //next item node = tmp; } }

From here

  • And, yes, @Schepalin, learn to google - The_Netos

Well, get on the first element, and going through the list, each of you expand the pointer to the previous node from which you just came. It is clear that the very first pointer is reset, and the list header now points to the node that was the last. Here is O(n) .