Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit98f2363

Browse files
authored
added iterative solution for 25 and new test cases (fishercoder1534#152)
1 parentdc7e06f commit98f2363

File tree

2 files changed

+81
-24
lines changed

2 files changed

+81
-24
lines changed

‎src/main/java/com/fishercoder/solutions/_25.java

Lines changed: 70 additions & 21 deletions
Original file line numberDiff line numberDiff line change
@@ -6,31 +6,80 @@ public class _25 {
66

77
/**We use recursion to go all the way until the end: when the number of nodes are smaller than k;
88
* then we start to reverse each group of k nodes from the end towards the start.*/
9-
publicListNodereverseKGroup(ListNodehead,intk) {
10-
ListNodecurr =head;
11-
intcount =0;
12-
while (curr !=null &&count !=k) {
13-
//find the k+1 node
14-
curr =curr.next;
15-
count++;
9+
publicstaticclassSolution1 {
10+
publicListNodereverseKGroup(ListNodehead,intk) {
11+
ListNodecurr =head;
12+
intcount =0;
13+
while (curr !=null &&count !=k) {
14+
//find the k+1 node
15+
curr =curr.next;
16+
count++;
17+
}
18+
19+
if (count ==k) {
20+
/**after this below recursive call finishes, it'll return head;
21+
* then this returned "head" will become "curr", while the head
22+
* in its previous callstack is the real head after this call.
23+
* Setting up a break point will make all of this crystal clear.*/
24+
curr =reverseKGroup(curr,k);
25+
26+
while (count-- >0) {
27+
ListNodetemp =head.next;
28+
head.next =curr;
29+
curr =head;
30+
head =temp;
31+
}
32+
head =curr;
33+
}
34+
returnhead;//we run out of nodes before we hit count == k, so we'll just directly return head in this case as well
1635
}
36+
}
37+
38+
publicstaticclassSolution2 {
39+
publicListNodereverseKGroup(ListNodehead,intk) {
40+
if (head ==null ||head.next ==null ||k ==1) {
41+
returnhead;
42+
}
43+
44+
intn =0;// number of nodes
45+
46+
ListNodecurr =head;
47+
while(curr !=null){
48+
n ++;
49+
curr =curr.next;
50+
}
51+
52+
ListNodeprev =null;
53+
ListNodenext =null;
54+
ListNodenewHead =null;
55+
ListNodetail1 =null;
56+
ListNodetail2 =head;
57+
58+
curr =head;
1759

18-
if (count ==k) {
19-
/**after this below recursive call finishes, it'll return head;
20-
* then this returned "head" will become "curr", while the head
21-
* in its previous callstack is the real head after this call.
22-
* Setting up a break point will make all of this crystal clear.*/
23-
curr =reverseKGroup(curr,k);
24-
25-
while (count-- >0) {
26-
ListNodetemp =head.next;
27-
head.next =curr;
28-
curr =head;
29-
head =temp;
60+
while (n >=k) {
61+
// reverse nodes in blocks of k
62+
for (inti =0;i <k;i++) {
63+
// linked List reversal code
64+
next =curr.next;
65+
curr.next =prev;
66+
prev =curr;
67+
curr =next;
68+
}
69+
if (newHead ==null) {
70+
newHead =prev;
71+
}
72+
if (tail1 !=null) {
73+
tail1.next =prev;
74+
}
75+
tail2.next =curr;// when n is not multiple of k
76+
tail1 =tail2;
77+
tail2 =curr;
78+
prev =null;
79+
n -=k;
3080
}
31-
head =curr;
81+
returnnewHead;
3282
}
33-
returnhead;//we run out of nodes before we hit count == k, so we'll just directly return head in this case as well
3483
}
3584

3685
}

‎src/test/java/com/fishercoder/_25Test.java

Lines changed: 11 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -9,14 +9,16 @@
99
importstaticorg.junit.Assert.assertEquals;
1010

1111
publicclass_25Test {
12-
privatestatic_25test;
12+
privatestatic_25.Solution1test;
13+
privatestatic_25.Solution2test2;
1314
privatestaticListNodeactual;
1415
privatestaticListNodeexpected;
1516
privatestaticListNodehead;
1617

1718
@BeforeClass
1819
publicstaticvoidsetup() {
19-
test =new_25();
20+
test =new_25.Solution1();
21+
test2 =new_25.Solution2();
2022
}
2123

2224
@Test
@@ -26,5 +28,11 @@ public void test1() {
2628
expected =LinkedListUtils.contructLinkedList(newint[]{2,1,4,3,5});
2729
assertEquals(actual,expected);
2830
}
29-
31+
@Test
32+
publicvoidtest2() {
33+
head =LinkedListUtils.contructLinkedList(newint[]{1,2,3,4,5,6,7});
34+
actual =test2.reverseKGroup(head,4);
35+
expected =LinkedListUtils.contructLinkedList(newint[]{4,3,2,1,5,6,7});
36+
assertEquals(actual,expected);
37+
}
3038
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp