Some c++ solution


  • 0
    N
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode * reverseKGroup(ListNode * head, int k) {
            
           // empty list case
           if( !head )
           {
               return head;
           }
            
           // count number of nodes
           int length = 0;
           for( ListNode * tmp = head; tmp != NULL; tmp = tmp->next, ++length ) ;
            
           // number of nodes is less than k, nothing should be reversed
           if( length < k )
           {
               return head;
           }
            
           // reverse first k-nodes 
           ListNode * prev = NULL; 
           ListNode * next = head->next;
           head->next = prev; 
           int cnt = 0;     
           ListNode * globalTail = head;       
           while( next && ( ++cnt % k ) )
           {
               prev = head;
               head = next;
               next = head->next;
               head->next = prev;
           }
            
           // set global head to be returned
           ListNode * globalHead = head;
            
           // reverse the rest nodes which should be reversed
           while( next && (length - cnt) / k )
           {     
               head = next;
               next = head->next;
               head->next = NULL;
               ListNode * tail = head;
    
               while( next && ( ++cnt % k ) )
               {
                   prev = head;
                   head = next;
                   next = head->next;
                   head->next = prev;
               }
    
               globalTail->next = head;
               globalTail = tail;
           }
            
           // connect tail which shouldn't be reversed
           if( length > cnt )
           {
               globalTail->next = next;
           }
            
           return globalHead;
        }
    };```

Log in to reply
 

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