|
| 1 | +packagemedium; |
| 2 | + |
| 3 | +importutils.CommonUtils; |
| 4 | +importclasses.ListNode; |
| 5 | + |
| 6 | +publicclassReverseLinkedListII { |
| 7 | + |
| 8 | +// then I turned to Discuss and find this most upvoted solution: |
| 9 | +// https://discuss.leetcode.com/topic/8976/simple-java-solution-with-clear-explanation, it's |
| 10 | +// indeed concise, I knew there's such a solution there |
| 11 | +publicListNodereverseBetween_concise_version(ListNodehead,intm,intn) { |
| 12 | +// use four nodes, pre, start, then, dummy |
| 13 | +// just reverse the nodes along the way |
| 14 | +ListNodedummy =newListNode(-1); |
| 15 | +dummy.next =head; |
| 16 | +ListNodepre =dummy; |
| 17 | +for (inti =0;i <m -1;i++) { |
| 18 | +pre =pre.next; |
| 19 | + } |
| 20 | + |
| 21 | +ListNodestart =pre.next;// start is the node prior to reversing, in the given example, |
| 22 | +// start is node with value 1 |
| 23 | +ListNodethen =start.next;// then is the node that we'll start to reverse, in the given |
| 24 | +// example, it's 2 |
| 25 | + |
| 26 | +for (inti =0;i <n -m;i++) { |
| 27 | +// pay special attention to this for loop, it's assigning then.next to start.next, it |
| 28 | +// didn't initialize a new node |
| 29 | +// this does exactly what I desired to do, but I just didn't figure out how to implement |
| 30 | +// it, thumbs up to the OP! |
| 31 | +start.next =then.next; |
| 32 | +then.next =pre.next; |
| 33 | +pre.next =then; |
| 34 | +then =start.next; |
| 35 | + } |
| 36 | + |
| 37 | +returndummy.next; |
| 38 | + } |
| 39 | + |
| 40 | +publicListNodereverseBetween(ListNodehead,intm,intn) { |
| 41 | +// find node at position m, let's call it "revHead" |
| 42 | +// set its previous node as "newRevHead", then start processing until we reach node at |
| 43 | +// position n |
| 44 | +ListNodenewRevHead =null,revHead =head,pre =newListNode(-1); |
| 45 | +pre.next =head; |
| 46 | +if (m >1) { |
| 47 | +intmCnt =1; |
| 48 | +while (mCnt++ <m) { |
| 49 | +newRevHead =revHead; |
| 50 | +revHead =revHead.next; |
| 51 | + } |
| 52 | + } |
| 53 | +ListNodenode_prior_to_m =newRevHead; |
| 54 | + |
| 55 | +// iteratively |
| 56 | +intnCnt =m; |
| 57 | +ListNodenext =null; |
| 58 | +while (nCnt <=n) { |
| 59 | +next =revHead.next; |
| 60 | +revHead.next =newRevHead; |
| 61 | +newRevHead =revHead; |
| 62 | +revHead =next; |
| 63 | +nCnt++; |
| 64 | + } |
| 65 | + |
| 66 | +if (nCnt >n) |
| 67 | +nCnt--; |
| 68 | +// append next to the tail of the reversed part |
| 69 | +ListNodereversedPart =newRevHead; |
| 70 | +if (reversedPart !=null) { |
| 71 | +while (nCnt >m) { |
| 72 | +reversedPart =reversedPart.next; |
| 73 | +nCnt--; |
| 74 | + } |
| 75 | +reversedPart.next =next; |
| 76 | + } |
| 77 | + |
| 78 | +// append the reversed part head to the node at position m-1 |
| 79 | +if (node_prior_to_m !=null) |
| 80 | +node_prior_to_m.next =newRevHead; |
| 81 | +else |
| 82 | +pre.next =newRevHead; |
| 83 | + |
| 84 | +returnpre.next; |
| 85 | + } |
| 86 | + |
| 87 | +publicstaticvoidmain(String...strings) { |
| 88 | +ReverseLinkedListIItest =newReverseLinkedListII(); |
| 89 | +// ListNode head = new ListNode(1); |
| 90 | +// head.next = new ListNode(2); |
| 91 | +// head.next.next = new ListNode(3); |
| 92 | +// head.next.next.next = new ListNode(4); |
| 93 | +// head.next.next.next.next = new ListNode(5); |
| 94 | +// int m = 2, n =4; |
| 95 | + |
| 96 | +// ListNode head = new ListNode(5); |
| 97 | +// int m = 1, n =1; |
| 98 | + |
| 99 | +ListNodehead =newListNode(3); |
| 100 | +head.next =newListNode(5); |
| 101 | +intm =1,n =2; |
| 102 | + |
| 103 | +CommonUtils.printList(head); |
| 104 | +ListNoderesult =test.reverseBetween(head,m,n); |
| 105 | +CommonUtils.printList(result); |
| 106 | + } |
| 107 | + |
| 108 | +} |