1
00:00:00,420 --> 00:00:06,990
‫Said, Now we're going to write our function to reverse a length list, and that function will start

2
00:00:06,990 --> 00:00:08,340
‫out like this.

3
00:00:08,340 --> 00:00:15,990
‫And this is a very common interview question to see if you can write the code to reverse a linked list

4
00:00:15,990 --> 00:00:17,280
‫in place.

5
00:00:17,640 --> 00:00:23,700
‫And this will by far be the most complicated function that we've seen so far in the course.

6
00:00:24,000 --> 00:00:28,350
‫So I'm going to bring up a linked list and walk through the steps to do this.

7
00:00:28,350 --> 00:00:34,470
‫So the first thing we'll do is reverse head and tail, and then we'll take each one of these pointers

8
00:00:34,470 --> 00:00:38,730
‫one by one and point them the other way like this.

9
00:00:38,730 --> 00:00:42,150
‫And this reverses the length list.

10
00:00:42,950 --> 00:00:48,080
‫So let's put this all back and we'll move this down to the bottom here.

11
00:00:48,410 --> 00:00:52,040
‫And the first thing we'll do is switch head and tail.

12
00:00:52,310 --> 00:00:58,970
‫And the way we'll do that is have a variable that we set equal to head and that we set head to be equal

13
00:00:58,970 --> 00:00:59,840
‫to tail.

14
00:01:00,170 --> 00:01:03,890
‫And then we set tail to be equal to temp.

15
00:01:04,370 --> 00:01:07,070
‫So let's write the code for these three steps.

16
00:01:07,700 --> 00:01:09,620
‫First, we create the variable temp.

17
00:01:09,620 --> 00:01:11,270
‫We set it equal to head.

18
00:01:12,090 --> 00:01:17,600
‫We set head to be equal to tail and tail equal to temp.

19
00:01:18,060 --> 00:01:22,050
‫So let's look at this in with the rest of our code so far.

20
00:01:22,470 --> 00:01:25,380
‫And now let's bring back our linked list.

21
00:01:25,770 --> 00:01:29,580
‫So in order to reverse this, we'll need a couple more variables.

22
00:01:29,790 --> 00:01:35,940
‫I'll call one after that goes after temp, and the other one I'll call before.

23
00:01:36,150 --> 00:01:42,570
‫And these three variables are going to move through the length list as we are reversing each one of

24
00:01:42,570 --> 00:01:43,320
‫these arrows.

25
00:01:43,320 --> 00:01:47,070
‫So I'm going to move this back and we'll create these two variables.

26
00:01:48,340 --> 00:01:55,000
‫We'll say that after his equal to temp next and before is equal to null pointer.

27
00:01:55,540 --> 00:01:58,660
‫And let's look at these two lines in with the rest of our code.

28
00:01:59,940 --> 00:02:02,460
‫And bring back our linked list.

29
00:02:02,970 --> 00:02:08,330
‫And this brings us to the really complicated part of reversing a linked list.

30
00:02:08,340 --> 00:02:12,480
‫I'm going to create a for loop that runs the length of the length list.

31
00:02:12,840 --> 00:02:20,760
‫And each time we run the for loop, we'll say after equals temp next, that is temp next.

32
00:02:20,760 --> 00:02:25,020
‫And you can see in this iteration after already is equal to temp next.

33
00:02:26,240 --> 00:02:29,630
‫And then we'll say temp next equals before.

34
00:02:30,230 --> 00:02:37,250
‫So temp next is this arrow going from the 11 to the three.

35
00:02:37,250 --> 00:02:39,500
‫And when we set it equal to before.

36
00:02:40,410 --> 00:02:44,550
‫It flips that over and points it the other way.

37
00:02:45,170 --> 00:02:53,300
‫And the thing that makes reversing a linked list complicated is as soon as you do this, you have just

38
00:02:53,300 --> 00:02:55,940
‫broken your linked list.

39
00:02:56,090 --> 00:02:59,960
‫The L1 node is not connected to the rest of the linked list.

40
00:02:59,960 --> 00:03:09,710
‫Once you do this so that we'll say before equals temp that moves that up and then temp is equal to after.

41
00:03:10,130 --> 00:03:17,270
‫So you have to have that after variable there to get temp to be able to cross over this gap.

42
00:03:18,080 --> 00:03:25,370
‫So these four lines of code in the for loop have to be exactly in this order or you will break your

43
00:03:25,370 --> 00:03:28,010
‫length list and this won't work.

44
00:03:28,460 --> 00:03:34,490
‫So now let's walk through this to the end will say after equals ten next and you can see that after

45
00:03:34,490 --> 00:03:43,790
‫has to move first because once you say temp next equals before you have that gap between the three node

46
00:03:43,790 --> 00:03:45,290
‫and the 23 node.

47
00:03:45,530 --> 00:03:51,620
‫So after has to already be across that gap before you do this line of code.

48
00:03:51,950 --> 00:03:59,870
‫Then we set before to be equal to temp and then we move temp across that gap and we'll do this again.

49
00:03:59,870 --> 00:04:08,270
‫We'll move up after temp next equals before we'll flip that arrow over before equals temp and temp equals

50
00:04:08,270 --> 00:04:08,750
‫after.

51
00:04:08,750 --> 00:04:11,240
‫And this will be the last time we run through this.

52
00:04:11,720 --> 00:04:19,730
‫We'll say after equals temp next, we'll temp next is this arrow here and that's equal to null pointer.

53
00:04:19,730 --> 00:04:27,710
‫So now after is equal to null pointer that will say temp next equals before that flips that last arrow

54
00:04:27,710 --> 00:04:32,600
‫over and the will say before equals temp and temp equals after.

55
00:04:32,930 --> 00:04:38,360
‫And now this for loop is done running and our linked list is reversed.

56
00:04:38,660 --> 00:04:45,710
‫So let's add this in with the rest of our code, and that is the entire reverse function.

57
00:04:46,100 --> 00:04:51,800
‫So we'll look at this code and a moment in V's code, and when we do, we'll create this length list

58
00:04:51,800 --> 00:04:57,200
‫one, two, three, four, and then we'll run reverse and print that out.

59
00:04:57,200 --> 00:05:00,110
‫And it should be four, three, two, one.

60
00:05:00,410 --> 00:05:04,250
‫So now let's flip over to VS Code and take a look at this.

61
00:05:04,820 --> 00:05:10,280
‫So there is our reverse function there and I'm going to scroll up so we can look at our main function

62
00:05:10,280 --> 00:05:10,760
‫here.

63
00:05:10,970 --> 00:05:12,800
‫And this creates our linked list.

64
00:05:12,800 --> 00:05:14,480
‫One, two, three, four.

65
00:05:14,480 --> 00:05:18,260
‫And with this line will print that out and I'll run this.

66
00:05:18,740 --> 00:05:20,720
‫And that gives us our linked list.

67
00:05:20,720 --> 00:05:22,370
‫One, two, three, four.

68
00:05:22,820 --> 00:05:25,280
‫So I'm going to come up here and add a line.

69
00:05:26,500 --> 00:05:29,380
‫And this will reverse our linked list.

70
00:05:29,380 --> 00:05:30,760
‫And I'll run this.

71
00:05:31,580 --> 00:05:35,420
‫And now you can see that it prints out for 3 to 1.

72
00:05:35,930 --> 00:05:39,680
‫And that is our function for reverse.