My O(N) time O(1) solution. Better Ideas?


  • -2
    Y
    public ListNode reverseKGroup(ListNode head, int k) {
            if (head == null)
                return null;
                
            ListNode prevHead=null, prevTail=null;
            ListNode cur=head, curHead = null;
       
            int c = 0;
            while(cur != null){
                ++c;
                ListNode next = cur.next;
                if (curHead == null){
                    curHead = cur;
                    c=1;
                } 
                
                if (c == k){
                    // Within each group, do a normal reverse
                    reverse(curHead, cur);
                    
                    // Link group with previous group
                    if (prevHead== null){
                        prevHead = cur;
                    }
                    if (prevTail!=null){
                        prevTail.next = cur;
                    }
                        prevTail=curHead;
                    
                    // Reset group count
                    curHead = null;
                }
                
                cur = next;
            }
            
            if (prevTail!=null){
                prevTail.next = curHead;
            }
            
            return prevHead == null? head:prevHead;
        }
        
        /**
         * Normal reverse, head and tail will be switched after return 
         */
        public void reverse(ListNode head, ListNode tail){
            if (head == tail)
                return;
            
            ListNode prev=null, cur=head, next=head.next;
            while(!cur.equals(tail)){
                cur.next = prev;
                prev = cur;
                cur = next;
                next = cur.next;
            }
            
            cur.next = prev;
        }

  • 0
    T

    Actually, the list is visited twice. A better solution only visit the list once. Refer to http://www.cnblogs.com/TenosDoIt/p/3794505.html


  • 0
    D

    This solution also visited nodes twice


Log in to reply
 

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