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

Commitfd548a8

Browse files
both iterative and recursive solutions for Reverse Linked List.
1 parentab11f6b commitfd548a8

File tree

1 file changed

+36
-4
lines changed

1 file changed

+36
-4
lines changed

‎EASY/src/easy/ReverseLinkedList.java

Lines changed: 36 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -4,8 +4,12 @@
44
importclasses.ListNode;
55

66
publicclassReverseLinkedList {
7-
//there's no reversion if the list is null or it contains only one node, so at a minimum, there should be 2 nodes
8-
publicListNodereverseList(ListNodehead) {
7+
//creating a newHead = null is a very common/smart way to handle such cases, the logic flows out very naturally:
8+
//create a new node called "next" to hold current head's next node
9+
//then we could redirect head's next pointer to point to newHead which is head's previous node
10+
//the above two steps finished the reversion, to continue this process until we reach the end of the original list,
11+
//we'll assign current "head" to new "newHead", and current "next" to be new "head" for the next iteration, here's the code
12+
publicListNodereverseList_iterative(ListNodehead) {
913
ListNodenewHead =null;
1014
while(head !=null){
1115
ListNodenext =head.next;
@@ -15,16 +19,44 @@ public ListNode reverseList(ListNode head) {
1519
}
1620
returnnewHead;
1721
}
22+
23+
//following the above iterative version, the recursive solution flows out so naturally, basically, we just replaced the while loop with a recursive function
24+
//still, a null newHead proves to be very helpful.
25+
publicListNodereverseList_recursive(ListNodehead) {
26+
ListNodenewHead =null;
27+
returnreverse(head,newHead);
28+
}
29+
30+
privateListNodereverse(ListNodehead,ListNodenewHead) {
31+
if(head !=null){
32+
ListNodenext =head.next;
33+
head.next =newHead;
34+
newHead =head;
35+
head =next;
36+
returnreverse(head,newHead);
37+
}
38+
elsereturnnewHead;
39+
}
40+
41+
//the above recursive function could of course be shortened to below, but the above one is just more intuitive and easier to follow and sort out your logic
42+
privateListNodereverse_more_concise(ListNodehead,ListNodenewHead) {
43+
if(head !=null){
44+
ListNodenext =head.next;
45+
head.next =newHead;
46+
returnreverse_more_concise(next,head);
47+
}elsereturnnewHead;
48+
}
1849

19-
publicstaticvoidmain(String...strings){
50+
publicstaticvoidmain(String...strings){
2051
ReverseLinkedListtest =newReverseLinkedList();
2152
ListNodehead =newListNode(1);
2253
head.next =newListNode(2);
2354
head.next.next =newListNode(3);
2455
head.next.next.next =newListNode(4);
2556
head.next.next.next.next =newListNode(5);
2657
CommonUtils.printList(head);
27-
ListNoderesult =test.reverseList(head);
58+
// ListNode result = test.reverseList_iterative(head);
59+
ListNoderesult =test.reverseList_recursive(head);
2860
CommonUtils.printList(result);
2961
}
3062

0 commit comments

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