Recursive easy to understand solution Java


  • 0
    T

    HEADS UP! This is slightly inefficient but might be a good starting point for people who are trying to come up with ideas on solving this problem.

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public ListNode reverseKGroup(ListNode head, int k) {
            if(head == null || head.next == null || k<2) return head;
            int count = k;
            
            ListNode tail = head;
            while(tail!=null && tail.next!=null && count>1){
                //traverse till the kth element
                count--;
                tail = tail.next;
            }
            if(count>1) return head; // if the list ended before reaching kth element, do not reverse nothing..
            ListNode temp = tail.next; // temp is the (k+1)st node
            ListNode reverse = reverseList(head, temp); // reverse until the kth
            ListNode t = reverse; // head node of the revers'ed list
            head.next = reverseKGroup(temp, k); // but we want to attach to the end of the reversed list.
            return reverse; //finally return the head of the reversed list.
        }
        
        // This just reverses the list within the given boundaries
        private ListNode reverseList(ListNode head, ListNode tail){
            if(head == null || head.next == null || head.next == tail) return head;
            ListNode curr = head;
            ListNode prev = null;
            
            while(curr!=null && curr!=tail){
                ListNode next = curr.next;
                curr.next = prev;
                prev = curr;
                curr = next;
            }
            return prev;
            
        }
    }

Log in to reply
 

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