Skip to content

added iterative solution for 25 and new test cases #152

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 1 commit into from
Feb 27, 2021
Merged

added iterative solution for 25 and new test cases #152

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
1 commit
Select commit
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
91 changes: 70 additions & 21 deletions src/main/java/com/fishercoder/solutions/_25.java
View file
Open in desktop
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
}

}
14 changes: 11 additions & 3 deletions src/test/java/com/fishercoder/_25Test.java
View file
Open in desktop
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);
}
}