Sunday, June 3, 2012

Reverse a Linked List Recursively and Iterately


struct ListNode {
    ListNode* next;
    int       data;
};

 
ListNode* reverseListResursive(ListNode* head) {

 //Initial
 if(head == NULL) return head;
 if((head->next)== NULL) return head;

 ListNode *newHead = reverseListResursive(head->next);
 head->next->next = head;
 head -> next = NULL;

 return newHead;
}

 
ListNode* reverseListNonResursive(ListNode* head) {

 //Initial
 if(head == NULL) return head;
 //if((head->next)== NULL) return head;

 ListNode *newHead = head;
 ListNode *tempNext = NULL;

 while(head) {
  newHead = head;
  head = head->next;
  newHead->next = tempNext;
  tempNext = newHead;
 }

 return newHead;
}


1 comment:

liming hu said...

All recursive algorithms can be in iterate format.