Would you like to inspect the original subtitles? These are the user uploaded subtitles that are being translated: 1 1 00:00:00,186 --> 00:00:02,672 (upbeat music) 2 2 00:00:02,672 --> 00:00:05,360 (computer keys clicking) 3 3 00:00:05,360 --> 00:00:08,356 Alright, so, let's get cracking on this solution. 4 4 00:00:08,356 --> 00:00:10,630 I'm in the Integer Linked Lists class 5 5 00:00:10,630 --> 00:00:13,560 that was included with the starter project. 6 6 00:00:13,560 --> 00:00:15,950 And here's the insert sorted method. 7 7 00:00:15,950 --> 00:00:19,060 So I'll just delete this comment 8 8 00:00:19,060 --> 00:00:22,390 and as we can see, it accepts an integer value. 9 9 00:00:22,390 --> 00:00:24,580 The first thing we need to do is check 10 10 00:00:24,580 --> 00:00:27,370 whether the list is empty, because if the list is empty 11 11 00:00:27,370 --> 00:00:29,660 we can obviously just insert the node. 12 12 00:00:29,660 --> 00:00:31,510 And the other thing that we're going to check 13 13 00:00:31,510 --> 00:00:34,820 is whether the first node in the list 14 14 00:00:34,820 --> 00:00:37,450 so if the list isn't empty, we're gonna check whether 15 15 00:00:37,450 --> 00:00:40,530 the first node in the list is greater than or equal to 16 16 00:00:40,530 --> 00:00:42,890 the value we're inserting because in that case 17 17 00:00:42,890 --> 00:00:45,440 we can just insert the new node 18 18 00:00:45,440 --> 00:00:46,660 at the head of the list. 19 19 00:00:46,660 --> 00:00:50,400 And so, we're gonna say if head equals null 20 20 00:00:50,400 --> 00:00:52,490 because that means that the list is empty 21 21 00:00:53,369 --> 00:00:55,140 or head.getvalue 22 22 00:00:56,650 --> 00:00:59,310 is greater than or equal to the value we want 23 23 00:00:59,310 --> 00:01:01,330 to insert in both of these cases 24 24 00:01:01,330 --> 00:01:04,020 we wanna just go ahead and just add the new value 25 25 00:01:04,020 --> 00:01:04,853 at the front. 26 26 00:01:04,853 --> 00:01:07,400 We'll just call our add to front method 27 27 00:01:07,400 --> 00:01:08,400 with the value 28 28 00:01:08,400 --> 00:01:09,310 and we're done 29 29 00:01:09,310 --> 00:01:11,010 and then of course we wanna return. 30 30 00:01:11,010 --> 00:01:13,000 And so if the list is empty, we just 31 31 00:01:13,000 --> 00:01:14,750 need to add this new value at the front 32 32 00:01:14,750 --> 00:01:17,660 cause it'll be in sorted order by default 33 33 00:01:17,660 --> 00:01:22,640 or if the head value is greater than or equal to the value 34 34 00:01:22,640 --> 00:01:25,720 then we also know that the correct, sorted position 35 35 00:01:25,720 --> 00:01:27,170 is right at the front of the list 36 36 00:01:27,170 --> 00:01:32,170 cause in the main method, we're always calling insert sorted 37 37 00:01:32,580 --> 00:01:34,730 so the assumption that we're making here 38 38 00:01:34,730 --> 00:01:36,810 and I'll put this in here assumption 39 39 00:01:39,240 --> 00:01:42,130 the list is sorted 40 40 00:01:42,130 --> 00:01:44,650 this wouldn't work, this part wouldn't work 41 41 00:01:44,650 --> 00:01:46,470 if the list was not sorted. 42 42 00:01:46,470 --> 00:01:48,130 Obviously, if the list wasn't sorted 43 43 00:01:48,130 --> 00:01:49,470 we wouldn't even call this method 44 44 00:01:49,470 --> 00:01:51,310 it wouldn't make a lot of sense. 45 45 00:01:51,310 --> 00:01:55,680 Okay, so assuming that we don't have one of those two cases 46 46 00:01:55,680 --> 00:01:58,030 so we're not going to be inserting the new value 47 47 00:01:58,030 --> 00:01:59,990 at the front of the list we then need 48 48 00:01:59,990 --> 00:02:01,853 to find the insertion point. 49 49 00:02:02,940 --> 00:02:04,990 So, let's find the insertion point. 50 50 00:02:04,990 --> 00:02:08,820 Now, one wrinkle here is that we have a singly linked list. 51 51 00:02:08,820 --> 00:02:10,410 So what we're gonna do is we're going 52 52 00:02:10,410 --> 00:02:13,040 to traverse the list looking for the first node 53 53 00:02:13,040 --> 00:02:15,080 with a value that's greater than or equal 54 54 00:02:15,080 --> 00:02:17,110 to the value that we want to insert. 55 55 00:02:17,110 --> 00:02:19,490 So let's say we find that node and so let's say 56 56 00:02:19,490 --> 00:02:21,850 we have a current node and that node 57 57 00:02:21,850 --> 00:02:25,210 is pointing to the node that has a value greater than 58 58 00:02:25,210 --> 00:02:27,690 or equal to the value we want to insert. 59 59 00:02:27,690 --> 00:02:30,120 Well, it's easy for us to create a new node 60 60 00:02:30,120 --> 00:02:33,950 and point that new node's next field to the current node 61 61 00:02:33,950 --> 00:02:37,520 but what about the previous node's next field? 62 62 00:02:37,520 --> 00:02:40,630 It's currently pointing to the current node 63 63 00:02:40,630 --> 00:02:42,670 and we need to change it's next field so that 64 64 00:02:42,670 --> 00:02:45,210 it can point to the node with the new value. 65 65 00:02:45,210 --> 00:02:47,380 But it's a singly linked list, so 66 66 00:02:47,380 --> 00:02:49,400 if we only have a pointer to current, 67 67 00:02:49,400 --> 00:02:51,500 there's no way for us to get back 68 68 00:02:51,500 --> 00:02:53,590 to the previous node in the list. 69 69 00:02:53,590 --> 00:02:55,160 So we're gonna have to have two fields 70 70 00:02:55,160 --> 00:02:58,420 one for traversing the list and then another field 71 71 00:02:58,420 --> 00:03:02,490 that's going to be one position behind the current field. 72 72 00:03:02,490 --> 00:03:05,160 And so, when we finally hit a node that has a value 73 73 00:03:05,160 --> 00:03:07,780 greater than or equal to the one we're inserting 74 74 00:03:07,780 --> 00:03:12,590 the previous field will be pointing to the node before that. 75 75 00:03:12,590 --> 00:03:14,740 We'll say integer node current 76 76 00:03:14,740 --> 00:03:17,710 this is the one we're gonna use to traverse the list 77 77 00:03:17,710 --> 00:03:20,290 it's gonna equal head.getNext 78 78 00:03:20,290 --> 00:03:22,900 we don't have to check head cause we already did that here. 79 79 00:03:22,900 --> 00:03:25,760 And so, if we're down here, we know that 80 80 00:03:25,760 --> 00:03:29,370 the value in head is less than the value we're inserting. 81 81 00:03:29,370 --> 00:03:31,120 So we don't need to check it again. 82 82 00:03:32,060 --> 00:03:32,893 But 83 83 00:03:34,460 --> 00:03:36,450 we're gonna have a previous and that's 84 84 00:03:36,450 --> 00:03:37,830 going to point to head. 85 85 00:03:37,830 --> 00:03:40,690 So when we start out, our current node is gonna start 86 86 00:03:40,690 --> 00:03:43,820 at the head, at head.getNext, that's the first 87 87 00:03:43,820 --> 00:03:46,270 value we're gonna check and our previous node 88 88 00:03:46,270 --> 00:03:49,020 is at head, our previous node is always going to be 89 89 00:03:49,020 --> 00:03:51,380 one behind the current node. 90 90 00:03:51,380 --> 00:03:54,330 And then we're gonna say while current is not equal to null 91 91 00:03:55,898 --> 00:03:59,030 and current.getValue 92 92 00:04:00,000 --> 00:04:02,580 is less than the value we're inserting 93 93 00:04:02,580 --> 00:04:05,190 because the moment we hit a value that's greater than 94 94 00:04:05,190 --> 00:04:07,850 or equal we wanna stop. 95 95 00:04:07,850 --> 00:04:11,570 While that's true, we're gonna set previous to current 96 96 00:04:13,170 --> 00:04:17,653 and we're gonna set current to current.getNext. 97 97 00:04:18,520 --> 00:04:23,430 And so by doing this, we're constantly keeping previous 98 98 00:04:23,430 --> 00:04:27,090 one back from where current is. 99 99 00:04:27,090 --> 00:04:28,790 And so when we drop out of the loop, 100 100 00:04:28,790 --> 00:04:30,523 there are two possibilities here. 101 101 00:04:30,523 --> 00:04:34,110 Current is null or current isn't null 102 102 00:04:34,110 --> 00:04:35,970 meaning that we've hit a node with a value that's 103 103 00:04:35,970 --> 00:04:38,610 greater than or equal to the value we want to insert. 104 104 00:04:38,610 --> 00:04:40,820 Now, we don't have to handle the special case 105 105 00:04:40,820 --> 00:04:43,070 of current being null, because 106 106 00:04:43,070 --> 00:04:45,980 we're not going to change anything in current. 107 107 00:04:45,980 --> 00:04:48,750 So we don't have to worry that oh, we've hit 108 108 00:04:48,750 --> 00:04:50,130 the end of the list. 109 109 00:04:50,130 --> 00:04:52,080 If we have hit the end of the list, 110 110 00:04:52,080 --> 00:04:53,810 that means that we're going to be inserting 111 111 00:04:53,810 --> 00:04:56,040 the new value as the last node in the list 112 112 00:04:56,040 --> 00:04:58,170 and that's fine. 113 113 00:04:58,170 --> 00:05:00,900 We don't have to worry about oh, if we're at the end 114 114 00:05:00,900 --> 00:05:03,010 of the list and we've gotta do something differently. 115 115 00:05:03,010 --> 00:05:05,000 We don't have to worry about that, as you'll see. 116 116 00:05:05,000 --> 00:05:08,060 We now need to create a node for the new value. 117 117 00:05:08,060 --> 00:05:10,500 We need to set that node's next field 118 118 00:05:10,500 --> 00:05:12,870 and we need to set the next field 119 119 00:05:12,870 --> 00:05:15,100 of whatever previous is pointing to 120 120 00:05:15,100 --> 00:05:17,120 to point to the new node. 121 121 00:05:17,120 --> 00:05:21,250 And so we'll say integerNode newNode equals 122 122 00:05:21,250 --> 00:05:26,240 new IntegerNode for the value 123 123 00:05:26,240 --> 00:05:28,453 and then we're gonna say newNode.setnext 124 124 00:05:31,144 --> 00:05:31,977 current 125 125 00:05:33,328 --> 00:05:36,343 because we're inserting the new node before 126 126 00:05:36,343 --> 00:05:37,176 the current node because we wanna insert in sorted order 127 127 00:05:39,100 --> 00:05:40,663 and we know that current has a value 128 128 00:05:40,663 --> 00:05:42,920 it's the first node we've seen that has a value 129 129 00:05:42,920 --> 00:05:44,860 that's greater than or equal to 130 130 00:05:44,860 --> 00:05:46,020 the value we wanna insert. 131 131 00:05:46,020 --> 00:05:49,400 So we're gonna insert the new node in front of current so 132 132 00:05:49,400 --> 00:05:51,320 its next field will point to current 133 133 00:05:51,320 --> 00:05:55,530 and now we have to handle the previous' next field. 134 134 00:05:55,530 --> 00:05:58,200 Because whatever previous is pointing to 135 135 00:05:58,200 --> 00:06:00,600 it now wants to point to the new node. 136 136 00:06:00,600 --> 00:06:03,340 So our previous.setNext newNode. 137 137 00:06:05,410 --> 00:06:08,223 And finally, we need to update the size. 138 138 00:06:09,480 --> 00:06:10,526 And that's it. 139 139 00:06:10,526 --> 00:06:14,030 If we were inserting this at the end of the list 140 140 00:06:14,030 --> 00:06:16,580 while current will be null, so it's perfectly fine 141 141 00:06:16,580 --> 00:06:19,400 for us to say, you know, newNode.setNext null 142 142 00:06:19,400 --> 00:06:21,540 it's sort of a redundant operation 143 143 00:06:21,540 --> 00:06:23,600 but it's not expensive so we'll just go ahead 144 144 00:06:23,600 --> 00:06:24,690 and do that. 145 145 00:06:24,690 --> 00:06:28,120 Let's go to our main method and in here 146 146 00:06:28,120 --> 00:06:31,360 we've created four integers, one, two, three and four 147 147 00:06:31,360 --> 00:06:34,320 and we're gonna insert three, two, one and four 148 148 00:06:34,320 --> 00:06:35,403 so let's run. 149 149 00:06:39,790 --> 00:06:43,100 And we'll see that we start out by inserting three 150 150 00:06:43,100 --> 00:06:46,510 and then we insert two so now we'll have two, three. 151 151 00:06:46,510 --> 00:06:48,950 We insert one so we'll have one, two, three 152 152 00:06:48,950 --> 00:06:50,810 and finally, we insert four. 153 153 00:06:50,810 --> 00:06:52,330 And so we have one, two, three, four 154 154 00:06:52,330 --> 00:06:53,830 that's exactly what we want. 155 155 00:06:53,830 --> 00:06:56,350 And you'll see that in the last case 156 156 00:06:56,350 --> 00:06:58,870 we were inserting at the end of the list. 157 157 00:06:58,870 --> 00:07:01,010 And we didn't run into any problems. 158 158 00:07:01,010 --> 00:07:03,680 So I think the only tricky part for this one 159 159 00:07:03,680 --> 00:07:05,790 which is why I wanted to use a single linked list 160 160 00:07:05,790 --> 00:07:08,300 was to realise that 161 161 00:07:08,300 --> 00:07:11,550 we need to have two fields now you might have come up 162 162 00:07:11,550 --> 00:07:12,900 with a different implementation 163 163 00:07:12,900 --> 00:07:16,050 there may be a way to do this without using two fields. 164 164 00:07:16,050 --> 00:07:19,220 You may be able to somehow be a couple of nodes back 165 165 00:07:19,220 --> 00:07:23,100 and be using .getNext .getNext but I like 166 166 00:07:23,100 --> 00:07:25,980 to write really clear code so I've done it this way 167 167 00:07:25,980 --> 00:07:27,150 using two fields. 168 168 00:07:27,150 --> 00:07:29,053 Alright, that's it for this challenge. 14655