Iterative Space O(1) Time O(N) with explanations


  • 0
    L
    public ListNode ReverseKGroup(ListNode head, int k) {
        ListNode trunkHead = new ListNode(0), trunkTail = trunkHead, newHead = null, newTail = null, cursor = head;
        for(int i = 0; i == 0 && head != null; cursor = head, newTail = newHead = null){
             //1. Check rest of nodes have at least K
            for(;i < k && cursor != null;i++) cursor = cursor.next;
            if (i != k) trunkTail.next = head; //2.2 Rest of nodes amount less than K, connect it directly
            else{
                //2.1 Move nodes from original list to new reversed list with head of variable "newHead"
                for (cursor = head; i > 0; i--){
                    head = cursor.next;
                    cursor.next = newHead;
                    newHead = cursor;
                    cursor = head;
                    if (i == k) newTail = newHead;
                }
                //3. Connect new reverseed list "newHead" to the whole reversed list with head of "trunkHead"
                trunkTail.next = newHead;
                trunkTail = newTail;
            }
        }
        return trunkHead.next == null ? head : trunkHead.next;
    }

Log in to reply
 

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