My code, non-recursive version, 30ms, with explanation O(n) complexity, O(1) space


  • -1
    D
    class Solution {
    public:
        ListNode *reverseKGroup(ListNode *head, int k) {
            ListNode dummy(0); // dummy head node to track the new head node
            ListNode *dummyH = &dummy; // pointing to the last node of the k-node sublink (after reverse) just before the current sublink
            if(k<=1 || !head) return head;
            ListNode *pre, *cur, *next, *start, *end;
            dummyH->next = head;
            int i;
            do{
                  start = end = dummyH->next;// start points to the first node of the current k-node sublink, end points to the last one
                  for(i=0;i<k-1;i++)
                  {// move end to the last node of the current k-node sublink
                      end = end->next;
                      if(!end) return dummy.next; // if the current sublink has less than k nodes, just return
                  }
                  dummyH->next = end; // link the last node of the previous k-node sublink (after reverse) to the last node of the current sublink (before reverse) 
                  dummyH =start; // update dummyH to starat, which is the last node of the current sublink after reverse
                  pre = start;
                  cur = pre->next;
                  while(pre!=end)
                  { // reverse the current k-node sublink
                      next = cur->next;
                      cur->next = pre;
                      pre = cur;
                      cur = next;
                  }
                  dummyH->next = next; // link the last node (after reverse) to the next unprocessed node
            }while(next);
            return dummy.next;
        }
    };

Log in to reply
 

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