C++ solution, no dummy head one pass solution


  • 0
    X
    class Solution {
    public:
        ListNode* reverseBetween(ListNode* head, int m, int n) {
          ListNode* pre = NULL, * cur = head; // cur is the current node, pre is the previous
          int i = 1;
          for (; i < m; i++) {
            pre = cur;
            cur = cur->next;
          }
          
          // now pre is the previous node before m, cur is m
          // reverse node until n
          ListNode* q = NULL, * p = cur;
          for (; i < n; i++) {
            ListNode* tmpNext = p->next;
            p->next = q;
            q = p;
            p = tmpNext;
          }
          
          // now q points to n-1, p points to n
          ListNode* mNext = p->next;
          p->next = q;
          
          // p points to n, cur points to m, pre points to m-1, maybe NULL
          if (pre) 
            pre->next = p;
          cur->next = mNext;
          
          // if pre is NULL, means reverse from the first element, now head is p;
          // if pre is not NULL, means reverse from at least the second element, now head is original head
          return pre == NULL ? p : head;
        }
    };

Log in to reply
 

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