Feb 27, 2021 · Feb 27, 2021
diff --git a/src/main/java/com/fishercoder/solutions/_25.java b/src/main/java/com/fishercoder/solutions/_25.java

    /**We use recursion to go all the way until the end: when the number of nodes are smaller than k;
     * then we start to reverse each group of k nodes from the end towards the start.*/
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode curr = head;
        int count = 0;
        while (curr != null && count != k) {
            //find the k+1 node
            curr = curr.next;
            count++;
    public static class Solution1 {
        public ListNode reverseKGroup(ListNode head, int k) {
            ListNode curr = head;
            int count = 0;
            while (curr != null && count != k) {
                //find the k+1 node
                curr = curr.next;
                count++;
            }

            if (count == k) {
                /**after this below recursive call finishes, it'll return head;
                 * then this returned "head" will become "curr", while the head
                 * in its previous callstack is the real head after this call.
                 * Setting up a break point will make all of this crystal clear.*/
                curr = reverseKGroup(curr, k);

                while (count-- > 0) {
                    ListNode temp = head.next;
                    head.next = curr;
                    curr = head;
                    head = temp;
                }
                head = curr;
            }
            return head;//we run out of nodes before we hit count == k, so we'll just directly return head in this case as well
        }
    }

    public static class Solution2 {
        public ListNode reverseKGroup(ListNode head, int k) {
            if (head == null || head.next == null || k == 1) {
                return head;
            }

            int n = 0; // number of nodes

            ListNode curr = head;
            while(curr != null){
                n ++;
                curr = curr.next;
            }

            ListNode prev = null;
            ListNode next = null;
            ListNode newHead = null;
            ListNode tail1 = null;
            ListNode tail2 =  head;

            curr = head;

        if (count == k) {
            /**after this below recursive call finishes, it'll return head;
             * then this returned "head" will become "curr", while the head
             * in its previous callstack is the real head after this call.
             * Setting up a break point will make all of this crystal clear.*/
            curr = reverseKGroup(curr, k);

            while (count-- > 0) {
                ListNode temp = head.next;
                head.next = curr;
                curr = head;
                head = temp;
            while (n >= k) {
                // reverse nodes in blocks of k
                for (int i = 0; i < k; i++) {
                    // linked List reversal code
                    next = curr.next;
                    curr.next = prev;
                    prev = curr;
                    curr = next;
                }
                if (newHead == null) {
                    newHead = prev;
                }
                if (tail1 != null) {
                    tail1.next = prev;
                }
                tail2.next = curr; // when n is not multiple of k
                tail1 = tail2;
                tail2 = curr;
                prev = null;
                n -= k;
            }
 head = curr;
 return newHead;
        }
        return head;//we run out of nodes before we hit count == k, so we'll just directly return head in this case as well
    }

 }
diff --git a/src/test/java/com/fishercoder/_25Test.java b/src/test/java/com/fishercoder/_25Test.java
 import static org.junit.Assert.assertEquals;

 public class _25Test {
    private static _25 test;
    private static _25.Solution1 test;
    private static _25.Solution2 test2;
    private static ListNode actual;
    private static ListNode expected;
    private static ListNode head;

    @BeforeClass
    public static void setup() {
        test = new _25();
        test = new _25.Solution1();
        test2 = new _25.Solution2();
    }

    @Test
        expected = LinkedListUtils.contructLinkedList(new int[]{2, 1, 4, 3, 5});
        assertEquals(actual, expected);
    }

    @Test
    public void test2() {
        head = LinkedListUtils.contructLinkedList(new int[]{1, 2, 3, 4, 5, 6, 7});
        actual = test2.reverseKGroup(head, 4);
        expected = LinkedListUtils.contructLinkedList(new int[]{4, 3, 2, 1, 5, 6, 7});
        assertEquals(actual, expected);
    }
 }
Original file line number	Diff line number	Diff line change
Expand Up		@@ -6,31 +6,80 @@ public class _25 {

		/**We use recursion to go all the way until the end: when the number of nodes are smaller than k;
		* then we start to reverse each group of k nodes from the end towards the start.*/
		public ListNode reverseKGroup(ListNode head, int k) {
		ListNode curr = head;
		int count = 0;
		while (curr != null && count != k) {
		//find the k+1 node
		curr = curr.next;
		count++;
		public static class Solution1 {
		public ListNode reverseKGroup(ListNode head, int k) {
		ListNode curr = head;
		int count = 0;
		while (curr != null && count != k) {
		//find the k+1 node
		curr = curr.next;
		count++;
		}

		if (count == k) {
		/**after this below recursive call finishes, it'll return head;
		* then this returned "head" will become "curr", while the head
		* in its previous callstack is the real head after this call.
		* Setting up a break point will make all of this crystal clear.*/
		curr = reverseKGroup(curr, k);

		while (count-- > 0) {
		ListNode temp = head.next;
		head.next = curr;
		curr = head;
		head = temp;
		}
		head = curr;
		}
		return head;//we run out of nodes before we hit count == k, so we'll just directly return head in this case as well
		}
		}

		public static class Solution2 {
		public ListNode reverseKGroup(ListNode head, int k) {
		if (head == null \|\| head.next == null \|\| k == 1) {
		return head;
		}

		int n = 0; // number of nodes

		ListNode curr = head;
		while(curr != null){
		n ++;
		curr = curr.next;
		}

		ListNode prev = null;
		ListNode next = null;
		ListNode newHead = null;
		ListNode tail1 = null;
		ListNode tail2 = head;

		curr = head;

		if (count == k) {
		/**after this below recursive call finishes, it'll return head;
		* then this returned "head" will become "curr", while the head
		* in its previous callstack is the real head after this call.
		* Setting up a break point will make all of this crystal clear.*/
		curr = reverseKGroup(curr, k);

		while (count-- > 0) {
		ListNode temp = head.next;
		head.next = curr;
		curr = head;
		head = temp;
		while (n >= k) {
		// reverse nodes in blocks of k
		for (int i = 0; i < k; i++) {
		// linked List reversal code
		next = curr.next;
		curr.next = prev;
		prev = curr;
		curr = next;
		}
		if (newHead == null) {
		newHead = prev;
		}
		if (tail1 != null) {
		tail1.next = prev;
		}
		tail2.next = curr; // when n is not multiple of k
		tail1 = tail2;
		tail2 = curr;
		prev = null;
		n -= k;
		}
		head = curr;
		return newHead;
		}
		return head;//we run out of nodes before we hit count == k, so we'll just directly return head in this case as well
		}

		}
Original file line number	Diff line number	Diff line change
Expand Up		@@ -9,14 +9,16 @@
		import static org.junit.Assert.assertEquals;

		public class _25Test {
		private static _25 test;
		private static _25.Solution1 test;
		private static _25.Solution2 test2;
		private static ListNode actual;
		private static ListNode expected;
		private static ListNode head;

		@BeforeClass
		public static void setup() {
		test = new _25();
		test = new _25.Solution1();
		test2 = new _25.Solution2();
		}

		@Test
Expand All		@@ -26,5 +28,11 @@ public void test1() {
		expected = LinkedListUtils.contructLinkedList(new int[]{2, 1, 4, 3, 5});
		assertEquals(actual, expected);
		}

		@Test
		public void test2() {
		head = LinkedListUtils.contructLinkedList(new int[]{1, 2, 3, 4, 5, 6, 7});
		actual = test2.reverseKGroup(head, 4);
		expected = LinkedListUtils.contructLinkedList(new int[]{4, 3, 2, 1, 5, 6, 7});
		assertEquals(actual, expected);
		}
		}