A new iterative solution - similar to reverse sentence but not words


  • 0
    D

    Simply put, reverse the order in k-block, and then a full reverse. See the example below which reverses in 2-block.

    1. Original: [1, 2], [3, 4], [5, 6], 7
    2. Reverse in two-block: 7, [5, 6], [3, 4], [1, 2]
    3. Reverse the full list: [2, 1], [4, 3], [6, 5], 7

    Here's the accepted codes.

        public ListNode reverseKGroup(ListNode head, int k) {
            if(k<=0 || head==null)
                return null;
            if(k==1 || head.next==null)
                return head;
    
            return reverseFull(revK(head, k));
        }
    
        // reverse in k-block.
        ListNode revK(ListNode head, int k) {
            ListNode newHead = null; // head of new list
            ListNode node = head;
            int count = 0;
            while(node != null) {
                count++;
                if(count % k == 0) {
                    ListNode oldHead = head;
                    head = node.next; // head point to remaining list
                    node.next = newHead; // the first k nodes list is inserted to the head of new list
                    newHead = oldHead;
                    node = head;
                    continue;
                }
                node = node.next;
            }
            if(count % k != 0) {
                // remaining less than k
                ListNode remainder = reverseFull(head);
                head.next = newHead;
                newHead = remainder;
            }
            return newHead;
        }
    
        // Fully reverse a linked list. Return head of new list.
        ListNode reverseFull(ListNode head) {
            // Each loop, remove head from the old list and insert to the head of new list.
            ListNode newHead = null; // head of the new list.
            while(head != null) {
                ListNode prev = head;
                head = head.next; // remove head from the old list.
                prev.next = newHead; // insert node prev into the head of new list.
                newHead = prev;
            }
            return newHead;
        }

Log in to reply
 

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