My C++ recursive solution and iterative solution with explanation


  • 1
    A
    //recursive solution
    ListNode *last = NULL;
    ListNode *head = NULL;
    ListNode* reverseList(ListNode *p)
    {
    	if(!p)   // if p is NULL
    		return NULL;
    	
    	if(p->next == NULL)   // last not NULL point
    	{
    		last = p;
    		head = p;
    	}
    	else
    		reverseList(p->next);
    	last->next = p;  // last is p's next pointer
    	p->next = NULL;
    	last = p;        // refresh last
    	return head;
    }
    
    // iterative solution
    ListNode* reverseList(ListNode *p)
    {
    	if( !p || !p->next )
    		return p;
    	ListNode *head = NULL;
    	while( p )
    	{
    		ListNode *q = p;   // q is temp pointer  
    		p = p->next;
    		q->next = head;
    		head = q;
    	}
    	return head;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.