Reverse the words in a string

Given an array of characters which form a sentence of words, give an
efficient algorithm to reverse the order of the words (not characters)
in it.

Answer:^[1]

Method 1:
I am a good boy
<------------->

yob doog  a   ma   I
<-> <--> <->  <-> <->

boy good a am I

Method2
Another way to do it is, allocate as much memory as the input for the final output. Start from the right of the string and copy the words one by one to the output.


Input  : I am a good boy
                     <--
                <-------
              <---------
           <------------
         <--------------
  

Output : boy
       : boy good
       : boy good a 
       : boy good a am 
       : boy good a am I 


The only problem to this solution is the extra space required for the output and one has to write this code really well as we are traversing the string in the reverse direction and there is no null at the start of the string to know we have reached the start of the string!. One can use the strtok() function to breakup the string into multiple words and rearrange them in the reverse order later.


Method3

Create a linked list like


+---+    +----------+    +----+    +----------+    +---+    +----------+ 
| I | -> |  | -> | am | -> |  | -> | a | -> |  | --+
+---+    +----------+    +----+    +----------+    +---+    +----------+   |
                                                                           |
                                                                           |
 +-------------------------------------------------------------------------+
 |
 |     +------+    +----------+    +-----+    +------+
 +---> | good | -> |  | -> | boy | -> | NULL | 
       +------+    +----------+    +-----+    +------+



Now its a simple question of reversing the linked list!.