Java Recursion Solution - Easy to understand (8 ms)


  • 0
    J
    // In each recursion, finding k nodes takes O(k) time; node reverse time is O(k), thus each recursion takes O(2k) time.
     // The recursion depth is n/k
     // Thus the total time is O(n)
     // Space cost is O(1)
     
    public class Solution {
        public ListNode reverseKGroup(ListNode head, int k) {
            if (head == null || head.next == null || k == 0 )  return head;
            
            ListNode start = head, end = head;
            int counter = 1;
            // Count k nodes
            while (end.next != null && counter < k) {
                end = end.next;
                counter++;
            }
            
            if (counter == k) { // If there exists k nodes, reverse them.
                ListNode next = end.next;       // Record the (k+1) th node
                reverser(start, end);           // Time O(k)
                start.next = reverseKGroup(next, k);        // start is now pointing to the tail of the reversed list. Recursion depth is n/k
                return end;
            }
            else {  // If there are less than k nodes, then return.
                return start;
            }
        }
        
        // Reverse list   (Time complexity O(k))
        private void reverser(ListNode start, ListNode end) {
            ListNode previous = null;
            while (start != end) {
                ListNode next = start.next;
                start.next = previous;
                previous = start;
                start = next;
            }
            start.next = previous;
        }
    }
    

Log in to reply
 

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