ProAnswers.org

How to reverse a linked list

How to reverse a linked list

Following is the implementation in C:




	
		
			
				
					
						01
					
						02
					
						03
					
						04
					
						05
					
						06
					
						07
					
						08
					
						09
					
						10
					
						11
					
						12
					
						13
					
						14
					
						15
					
						16
					
						17
					
						18
					
						19
					
						20
					
						21
					
						22
				
				
					
						
							typedef struct node{
						
							   int item;
						
							   struct node *next;
						
							}node;
						
							 
						
							void reverse(node *head){
						
							   node *prevn, *nextn, *currn;
						
							   prevn = nextn = currn = head;
						
							   prevn -> next = NULL;
						
							   currn = currn -> next;
						
							   nextn = currn -> next;
						
							 
						
							    for(;currn->next != NULL;){
						
							      currn -> next = prevn;
						
							      prevn = currn;
						
							      currn = nextn;
						
							      nextn = currn -> next;
						
							   }
						
							 
						
							    currn -> next = prevn;
						
							   head = currn;
						
							}
					
				
			
		
	



Here we use 3 pointers PREVN, CURRN, NEXTN which point to the previous node, current node and the next node respectively at any stage. Initially, they point to HEAD. We manipulate the pointers in the loop to reverse the links. At the end, we assign HEAD to CURRN(current node) as CURRN now points to first element (in the reversed list).