20-line iterative C++ solution


  • 46
    L
    -1 -> 1 -> 2 -> 3 -> 4 -> 5
     |    |    |    | 
    pre  cur  nex  tmp
    
    -1 -> 2 -> 1 -> 3 -> 4 -> 5
     |         |    |    | 
    pre       cur  nex  tmp
    
    -1 -> 3 -> 2 -> 1 -> 4 -> 5
     |              |    |    | 
    pre            cur  nex  tmp
    

    Above is how it works inside one group iteration(for example, k=3)

    class Solution {
    public:
        ListNode *reverseKGroup(ListNode *head, int k) {
            if(head==NULL||k==1) return head;
            int num=0;
            ListNode *preheader = new ListNode(-1);
            preheader->next = head;
            ListNode *cur = preheader, *nex, *tmp, *pre = preheader;
            while(cur = cur->next) 
                num++;
            while(num>=k) {
                cur = pre->next;
                nex = cur->next;
                for(int i=1;i<k;i++) {
                    tmp= nex->next;
                    nex->next = pre->next;
                    pre->next = nex;
                    cur->next = tmp;
                    nex = tmp;
                }
                pre = cur;
                num-=k;
            }
            return preheader->next;
        }
    };
    

    Thanks to ciaoliang1992, the tmp pointer is no necessary, so the more concise solution is

    class Solution {
    public:
        ListNode *reverseKGroup(ListNode *head, int k) {
            if(head==NULL||k==1) return head;
            int num=0;
            ListNode *preheader = new ListNode(-1);
            preheader->next = head;
            ListNode *cur = preheader, *nex, *pre = preheader;
            while(cur = cur->next) 
                num++;
            while(num>=k) {
                cur = pre->next;
                nex = cur->next;
                for(int i=1;i<k;++i) {
                    cur->next=nex->next;
                    nex->next=pre->next;
                    pre->next=nex;
                    nex=cur->next;
                }
                pre = cur;
                num-=k;
            }
            return preheader->next;
        }
    };

  • 3
    C

    very good code.
    But i think the ListNode *temp isn't necessary.
    You can change the loop:

            cur=pre->next;
            next=cur->next;
            for(int i=1;i<k;++i){
                cur->next=next->next;
                next->next=pre->next;
                pre->next=next;
                next=cur->next;
            }
            pre = cur;

  • 0
    S

    Very nice code , but shouldn`t you memory of the 'preheader' ?


  • 0
    L

    Ye you are right. I should delete the preheader. But I prefer smart pointer to do this, which is infeasible here so I just leave it there. (I don't like save it to a variable and delete it... I know I'm kind of paranoid on this...)


  • 13

    To not leak memory and to not have to delete preheader manually, you could just do this:

        ListNode preheader(-1);
        preheader.next = head;
        ListNode *cur = &preheader, *nex, *tmp, *pre = &preheader;
        .
        .
        .
        return preheader.next;
    

  • 0

    great thanks!!! I was wandering about it for a long time . Enlightened by your code!!!

    class Solution {
        public:
            ListNode* reverseKGroup(ListNode* head, int k) {
                if(!head||!head->next) return head;
                ListNode *head1=new ListNode(0);
                head1->next=head;
                ListNode *pre=head1,*start=pre->next,*end;
                int n=0;
                while(head)n++,head=head->next;
                while(n>=k){
                    for(int i=1;i<k;i++){
                        end=start->next;
                        start->next=end->next;
                        end->next=pre->next;
                        pre->next=end;
                    }
                    pre=start;
                    start=pre->next;
                    n-=k;
                }
                return head1->next;
            }
        };

  • 4
    F

    There's no need for the dummy head if a 'pointer to the pointer' is used. Plus we can avoid checking the remaining length (which effectively causes the list to be traversed twice instead of once) by simply reversing the last segment back when the end is reached:

    class Solution {
    public:
       ListNode* reverseKGroup(ListNode* head, int k) {
          if( k > 1 ) for(auto pp=&head; *pp;) pp = reverse(pp, k);
          return head;
       }
    private:
       ListNode** reverse(ListNode** pphead, int k) {
          auto ppnew = &((*pphead)->next);
          for(int kr=1; kr<k; kr++) {
             if( ! *ppnew ) return reverse(pphead, kr);
             auto pnext = (*ppnew)->next;
             (*ppnew)->next = *pphead;
             *pphead = *ppnew;
             *ppnew = pnext;
          }
          return ppnew;
       }
    };

  • 0
    M

    class Solution {

        public:
            ListNode* reverseKGroup(ListNode* head, int k) {
    
                ListNode *p1=head,*p2=head;
                ListNode *first=NULL,*cur=head;
                int n=0;
                while(p1)
                {
                    p1=p1->next;
                    n++;
                }
                n=n/k;
                if(n==0||k==1) return head;
                for(int i=0;i<n;i++)
                {
                    ListNode *prev=NULL,*next=NULL;
                    int l=1;
                    p1=cur;
                    while(l++<=k)
                    {
                        next=cur->next;
                        cur->next=prev;
                        prev=cur;
                        cur=next;
                    }
                    if(i>=1)
                        first->next=prev;
                    else
                        p2=prev;
                    first=p1;
                }
                first->next=cur;
                return p2;
            }
        };

  • -1
    Y

    Using stack to simplify the pointer operation,extra space is k* sizeof(ListNode*) ,it is constant.

    	ListNode* reverseKGroup(ListNode* head, int k) {
    		if (!head) return NULL;
    		stack<ListNode*>stack1;
    		int m = k, num = 0;
    		ListNode* p = head, dummy(0), *pcur = &dummy;
    		while (p) {
    			++num;
    			p = p->next;
    		}
    		p = head;
    		while (num >= k) {
    			m = k;
    			while (m--) {
    				stack1.push(p);
    				p = p->next;
    			}
    			m = k;
    			while (m--) {
    				pcur->next = stack1.top();
    				stack1.pop();
    				pcur = pcur->next;
    				pcur->next = NULL;
    			}
    			num -= k;
    		}
    		if (p) pcur->next = p;
    		return dummy.next;
    	}
    

  • -1
    K
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode *LNptp=head,*LNptp2=head;
        while(1){
            LNptp2=LNptp;
            vector<int> vi;
            int i=0;
            for(i=0;i<k;i++){
                if(LNptp==NULL) break;
                vi.push_back(LNptp->val);
                LNptp=LNptp->next;
            }
            if(i<k) break;
            for(i=k-1;i>=0;i--){
                LNptp2->val=vi[i];
                LNptp2=LNptp2->next;
            }
        }
        return head;
    }
    

  • 0
    L

    My Java version of the same. Hope it helps.

    public class Solution {
        public ListNode reverseKGroup(ListNode head, int k) {
            if(head == null || k == 1) return head;
            ListNode dummy = new ListNode(0);
            dummy.next = head;
            ListNode cur = dummy , nex = dummy, pre = dummy;
            int count = 0;
            while(cur.next != null){
                cur = cur.next;
                count++;
            }
            while(count >= k){
                cur = pre.next;
                nex = cur.next;
                for(int i = 1; i < k; i++){
                    cur.next = nex.next;
                    nex.next = pre.next;
                    pre.next = nex;
                    nex = cur.next;
                }
                pre = cur;
                count-=k;
            }
            return dummy.next;
        }
    }
    

  • 0
    Q

    My C++ Solution.

    ListNode* reverseKGroup(ListNode* head, int k) {
    		int n=0;
    		ListNode* cur=head, *tmp=0, *previous =0, *next =0, *lastTail=0, *previousTail=0;
    		if (head == 0 || k <= 1)
    			return head;
    		while (cur != 0)
    		{
    			n++;
    			cur = cur->next;
    		}
    		int groups = n / k;
    		cur = head;
    		bool newHeadFound = false;
    		previous = 0;
    		for (int i = 0; i < groups; i++)
    		{	
    			lastTail = 0;
    			for (int j = 0; j < k; j++)
    			{
    				next = cur->next;
       			    cur->next = previous;
    				previous = cur;
    				if (lastTail == 0)
    				{
    					lastTail = cur;
    				}
    				cur = next;
    			}
    			if (!newHeadFound)
    			{
    				head = previous;
    				newHeadFound = true;
    			}
    			if (previousTail != 0)
    				previousTail->next = previous;
    			previousTail = lastTail;
    		}
    		if (n>k)
    			lastTail->next = cur;
    		return head;
    
    	}
    

Log in to reply
 

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