Reverse a linked list without using temporary variables
How To Reverse a Linked List (3 Different Ways)Rate me: Please Sign up or sign in to vote. 3.72/5 (13 votes) GPL32 min read The purpose of this article is to show how to reverse a linked list IntroductionThere are acouple of ways to reverse a linked list. One of them requires knowledge of pointersand one of them is pretty straight forward. In this article, 3 different methods of reversing a linked listare demonstrated. All the linked list reversing algorithms assume that the given linked list is a double linked list. Show Technique 1In this way, a new linked list will be created and all the items of the first linked list will be added to the new linked list in reverse order.C# Copy Code This way is probably the most inefficient among the three. Even though objects of each node are not copied to memory, a new link list node is created for each call to Add property. A new link list node means at least 3 pointers (Next, Previous, Item) will be created for each item. This method not only wastes memory, but also wastes processing power. Technique 2In this method, we will swap linked list node objects (references to the data). Swapping starts from the first nodes object and the first nodes object is swapped with the last nodes object. Then, the second nodes object is swapped with the one before the last nodes object. Assuming we have N nodes in the link list:
After swapping: Swapping goes on until the middle of the linked list is found. C# Copy Code This way of reversing a linked list is pretty optimized and pretty fast. The only overhead of this algorithm is finding the end of the linked list. Technique 3In this way, the head of the linked list will point to the last node of the linked list. Also, each nodes Next and Previous properties need to be swapped too. Next(red arrow) and Previous(blue arrow) are swapped: C# Copy Code This method of reversing the linked list is performed in a single traverse through the link list. This way is more optimized than the second method. If the reversing requires to keep the link list nodes at their same position, technique 2 will fail. ConclusionMethod 1 is the most straight forward and it can be implemented pretty quickly. However it uses lots of system resources. Every time a new node is added, a new memory in the heap will be reserved.Method 2 is pretty professional but if link list doesnt keep track ofits tail, link list will be traversed twice. In this case, it will be slower thanmethod 3. Method 3 is the most professional and the fastest one. Original article can be found here. LicenseThis article, along with any associated source code and files, is licensed under The GNU General Public License (GPLv3) ShareAbout the Author
Interests: Operating Systems Embedded Systems .Net Framework C# Asp.net Eduation: MS Computer Science |