O(n) iterative solution with java


  • 0
    L

    Using two pointers to track the local head

    public ListNode reverseKGroup(ListNode head, int k) {
        if(head == null) return null;
        if(head.next == null) return head;
        if(!forward(head, k)) return head;
        int count=1;
        ListNode globalHead = null;
        ListNode localHead = head;
        ListNode prevLocalHead = null;
        ListNode prev = null;
        ListNode curr = head;
        while(curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
            if(count % k == 0) {
                if(globalHead == null) {
                    globalHead = prev;
                }
                if(prevLocalHead != null) {
                    prevLocalHead.next = prev;
                }
                prevLocalHead = localHead;
                localHead.next = curr;
                localHead = curr;
                if(!forward(curr, k)) break;
            }
            count++;
        }
        
        return globalHead;
    }
    
    public boolean forward(ListNode node, int k) {
        ListNode temp = node;
        for(int i=1;i<k;++i) {
            if(temp == null) break;
            temp = temp.next;
        }
        return temp != null;
    }
    

Log in to reply
 

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