Easily understood solution~


  • 0

    The task is reversing a list in range m to n(92) or a whole list(206).

    All in one : U need three pointers to achieve this goal.

    1) Pointer to last value

    2) Pointer to cur p value

    3) Pointer to next value

    Here, showing my code wishes can help u.

    Of course, you also need to record four nodes in special postions.

    1) newM  2)newN  3)beforeM  4)afterN

    These may be some complex(stupid) but it's really friend to people who are reading my code and easily understood.

    ListNode* reverseBetween(ListNode* head, int m, int n) {
    	if(m == n || head == NULL) return head;
    	ListNode *pLast = head, *p = head -> next, *pNext = NULL;
    	ListNode *newN = NULL, *newM = NULL, *beforeM = head, *afterN = NULL;
    	int pos = 1;
    	while(p){
    		if(pos == m - 1){
    			beforeM = pLast;
    			pLast = p;
    			p = p -> next;
    		}
    		else if(pos >= m && pos < n){
    			pNext = p -> next;
    			p -> next = pLast;
    			if(pos == m){
    				pLast -> next = NULL;
    				newM = pLast;
    			}
    			pLast = p;
    			if(pos == n - 1){
    				newN = p;
    				afterN = pNext;
    			}
    			p = pNext;
    		}else{
    			pLast = p;
    			p = p -> next;
    		}
    		pos ++;
    	}
    	if( m==1 && afterN == NULL){
    		head = newN;
    	}else if(m == 1){
    		head = newN;
    		newM -> next = afterN;
    	}else{
    		beforeM -> next = newN;
    		newM -> next = afterN;
    	}
    	return head;
    }
    
    ListNode* reverseList(ListNode* head) {
    	if(head == NULL) return head;
    	ListNode *pLast = head, *p = head -> next, *pNext = NULL;
    	while(p){
    		pNext = p -> next;
    		p -> next = pLast;
    		if(pLast == head){
    			pLast -> next = NULL;
    		}
    		pLast = p;
    		p = pNext;
    	}
    	head = pLast;
    	return head;
    }

Log in to reply
 

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