Iterative (Approach is same as "Reverse a linked list from position m to n")


  • 0
    P
    class Solution {
        public ListNode reverseKGroup(ListNode head, int k) {
            int n = length(head);
            if(k > n)
                return head;
            //reverse the first part (1...k) 
            ListNode result = reverse(head, 1, k);
            //now for next reversal our head becomes result
            head = result;
            //We need to reverse k parts until we reach end, which is (n/k) times
            for(int i = 1; i < n/k; i++){
                //need to move our head pointer, first time for k-1 times and k times otherwise
                int cnt = (i > 1) ? k : k - 1;
                while(cnt > 0){
                    head = head.next;
                    cnt--;
                }
                head.next = reverse(head.next, i*k+1, (i+1)*k);
            }
            return result;
        }
        static ListNode reverse(ListNode node, int left, int right){
            ListNode rev = null, first = node, second;
            while(left <= right){
                second = first.next;
                first.next = rev;
                rev = first;
                first = second;
                left++;
            }
            node.next = first;
            return rev;
        }
        static int length(ListNode node){
            int l = 0;
            while(node != null){
                node = node.next;
                l++;
            }
            return l;
        }
    }
    

Log in to reply
 

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