0ms C solution, simple and easy to comprehend.


  • 0
    X

    Since the List given by OJ doesn't have a leading node, I create a sentinel node for convenient.

    struct ListNode* reverseBetween(struct ListNode* head, int m, int n) {
        if (head == NULL || m == n)
    		return head;
    
    	struct ListNode sentinel;  /* Create a sentinel node for the list */
    	sentinel.next = head;
    	struct ListNode *m_preceding = &sentinel;  /* Position of the node precedes m */
    	int count = 0;  /* Counter */
    	int distance = n - m;  /* Times needed to reverse the internal list [m,n] */
    	
    	while (count++ < m-1)  /* Find the node precedes m */
    		m_preceding = m_preceding->next;
    
    	struct ListNode *p = m_preceding->next;  /* p points to node m */
    	struct ListNode *q = p->next;  /* q points to the node next to m */
    	
    	for (count = 0; count < distance; count++)  /* Step1, reverse the list between [m,n] iteratively */
    	{
    		struct ListNode *temp = q->next;  /* Save the address of the node succeeds n */
    		q->next = p;  /* Successor points to the predecessor */
    		p = q;  /* Move p downward one spot */
    		q = temp;  /* Move q doward one sopt */
    	}
    	m_preceding->next->next = q;  /* Step2, fix node m pointing to the node after n originally */
    	m_preceding->next = p;  /* and the node precedes m pointing to n */
    
    	return sentinel.next;
    }
    

    If you have any better advises to improve this program, please let me know.
    Thanks, xiyu.


Log in to reply
 

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