Clone given Linked List

Write a function that takes a singly linked list and returns a complete copy of that list.


 


 

Simple Approach

The idea is to iterate over the original list in the usual way and maintain two pointers to keep track of the new list: one head pointer, and one tail pointer which always points to the last node in the new list. The first node is done as a special case, and then the tail pointer is used in the standard way for the others.

 
C++ implementation –
 

Download   Run Code

Output:

1 -> 2 -> 3 -> 4 -> null

 


 

Using push()

The above implementation is a little unsatisfying because the 3-step-link-in is repeated — once for the first node and once for all the other nodes. Below function uses Push() to take care of allocating and inserting the new nodes, and so avoids repeating that code.

 
C++ implementation –
 

Download   Run Code

Output:

1 -> 2 -> 3 -> 4 -> null

 


 

Using Dummy Node

Another strategy is to use a temporary dummy node to take care of the first node case. The dummy node is temporarily the first node in the list, and the tail pointer starts off pointing to it. All nodes are added off the tail pointer.

 
C++ implementation –
 

Download   Run Code

Output:

1 -> 2 -> 3 -> 4 -> null

 


 

Using Local References

The final, and most unusual version uses the “local references” strategy instead of a tail pointer. The strategy is to keep a lastPtr that points to the last pointer in the list. All node additions are done at the lastPtr, and it always points to the last pointer in the
list. When the list is empty, it points to the head pointer itself. Later it points to the .next pointer inside the last node in the list.

 
C++ implementation –
 

Download   Run Code

Output:

1 -> 2 -> 3 -> 4 -> null

 


 

Recursive Solution

Finally, for completeness, here is the recursive version of CopyList(). It has the pleasing shortness that recursive code often has. However, it is probably not good for production code since it uses stack space proportional to the length of its list.

 
C++ implementation –
 

Download   Run Code

Output:

1 -> 2 -> 3 -> 4 -> null

 
Source:
http://cslibrary.stanford.edu/103/LinkedListBasics.pdf

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz