C solution with comments


  • 0
    Z
    typedef struct ListNode ln;
    
    /* terminology
       0 -> 1 -> 4 -> 3 -> 2 -> 5 -> NULL
       0 is the sentinel node created
       1 is the preceding list (since only one node, 1 is also the tail of the preceding list)
       4 3 2, 3 nodes reverse list
       5 is the head of following list
    */
    
    ln* reverseBetween(ln* head, int m, int n) {
      int k=n-m+1;// preceding steps and reverse steps
    
      ln newH; // sentinel node
      newH.next = head;
      ln* p = &newH;
      
      while(m-- >1) p = p->next; // preceding traverse
    
      ln *pp = p, *t=p->next; // pp is the previous node and t is the tail node after reverse 
    
      head = p; // head stores the tail of preceding list
      p = p->next;
    
      while(k>0)
      {
        // swap p and pp
        ln* next = p->next;
        p->next = pp;
        pp = p;
        p=next;
        k--;
      }
      
      head->next = pp; // tail of preceding list points to the new head of reverse list
      t->next = p; // tail of the reverse list points to the head of following list
    
      return newH.next; // return the new head after sentinel node
    }

Log in to reply
 

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