Reverse a Linked List | Iteratively & Recursively | DSA-One Course #37

Aug 15, 2023

Reverse a Linked List | Iteratively & Recursively | DSA-One Course #37

Hey guys, In this video, We’re going to solve a famous problem on Linked List known as Reverse a Linked List. We’ll solve it using both the Iterative and Recursive approach.

Practice problems here: https://www.interviewbit.com/courses/…

🥳 Join our Telegram Community:
Telegram channel: https://telegram.me/realanujbhaiya
Telegram group: https://telegram.me/dsa_one

🚀 Follow me on:
Instagram: https://www.instagram.com/Anuj.Kumar…
Linkedin: https://www.linkedin.com/in/sharma-ku…
Twitter: https://twitter.com/realanujbhaiya

💸 Use coupon code ANUJBHAIYA on GeeksforGeeks to avail discounts on courses!

📚 Complete DSA Playlist: • DSA-One Course - The Complete Data St…

Complete Android Development Playlist: • Android Development Tutorial for Begi…

Hashtags:
#anujbhaiya #dsaone

Ignore these tags:

reverse a linked list
reverse linked list
linked list
how to reverse a linked list
reverse a singly linked list
reverse a linked list using recursion
reverse a linkedlist
linked lists
reverse a link list
reverse a linked list in java
code to reverse a linked list
linked list reverse
reverse
reverse linked list java
reverse linked list leetcode
reverse linked list javascript
reverse linked list iteratively
reversed linked list
reverse a linked list java
reverse a linked list
reverse a linked list - iterative method
reverse linked list iteratively
linked list
how to reverse a linked list
reverse linked list
iterative method to reverse a linked list
reverse a singly linked list
code to reverse a linked list
reverse a linked list using recursion
reverse a link list
reverse a linked list in java
linked list reverse
reverse linked list java
reverse a linkedlist
reverse linked list leetcode
reverse a linked list
reverse linked list
reverse a linked list using recursion
linked list
reverse a singly linked list
how to reverse a linked list
code to reverse a linked list
reverse linked list recursively
linked list reverse
reverse a singly linked list c program
reverse a linked list - iterative method
iterative method to reverse a linked list
how to reverse a linked list recursively
reverse a singly linked list recursively
reverse linked list leetcode
linked list
reverse a linked list
reverse linked list
linked list reverse
reverse a singly linked list
reverse linked list java
singly linked list
linked list reversal
java
reverse linked list ii
doubly linked list
reverse linked list leetcode
how to reverse a linked list
reverse doubly linked list
leetcode reverse linked list ii
reverse a linked list using recursion
reverse
reverse linked list java code
linked lists
linked list reverse in java

Content

0 -> Hey what's up guys Anuj here &

1.094 -> Welcome to DSA one course

2.238 -> & in today's video, we will be talking about an important question in linked list

4.976 -> which is reverse a linked list

6.235 -> basically you are given a linked list

7.981 -> you have to reverse it

9.462 -> first the linked list was, 10, 20, 15, 4

12.319 -> then it will be reversed as 4, 15, 20 & 10

15.409 -> first head was 10

16.777 -> now head will point the last one

18.813 -> head will point to 4

20.126 -> so basically you are given a linked list & you have to reverse it

22.784 -> this question looks very simple

25.048 -> but I have seen that when this is asked in the interviews

28.75 -> so many experienced people also gets confused here

30.877 -> while coding this

32.03 -> so why am I explaining this question in linked list so initially

35.4 -> because you have to understand pointers properly in linked list

38.464 -> we have to understand how we have to assign temporary variables

43.777 -> so that my node does not get lost

45.888 -> so for that this question is very important

48.536 -> so let's see one more example of this

50.438 -> so if there are only two nodes in your linked list

53.073 -> 20 & 5

54.436 -> so it will be reversed to 5 & 20

56.47 -> first head was pointing 20,

57.969 -> now it will point 5

58.96 -> similarly, if there is only one node in linked list, 10

61.786 -> which is the head

62.702 -> so it will remain the same as

64.101 -> even if you reverse it, it will remain the same

67.046 -> so this is the question

68.254 -> hope you understood the question

69.105 -> it's basically reverse a linked list

70.589 -> it is a very famous & generic problem

72.562 -> we will solve it today

74.164 -> there are two ways for that

75.053 -> one is the iterative way

76.443 -> one is recursive way

77.501 -> we will understand both of them

79.035 -> logic is very simple in this

80.564 -> first we will start with a linked list where

82.713 -> we have only one node

83.874 -> if there is only one node &

84.849 -> i ask you to reverse it,

86.253 -> so you can say that it is already reversed

87.968 -> there is only one node & we will return the same

90.019 -> it is already reversed

91.288 -> so now I tell you that suppose you have two nodes instead of one

95.017 -> then what will you do?

95.671 -> one node is '1' & the other node is '2'

97.334 -> next of 1 is pointing at 2

98.915 -> and suppose for now, next of 2 is pointing at null

101.115 -> so how will you reverse it?

102.971 -> you will tell me that,

105.363 -> let's point the next for 2 towards 1

108.134 -> means, instead of pointing null, it will point 1

111.243 -> and the next of 1 that was initially pointing towards 2

113.663 -> now instead of 2, it will point null

117.446 -> so here the linked list is reversed

119.893 -> initially it was 1 to 2,

121.004 -> now you can see it is 2 to 1 pointer

122.214 -> so the linked list is reversed

123.535 -> now suppose we add one more element

125.603 -> suppose instead of pointing null,

127.802 -> suppose it was pointing 3

130.548 -> there was a third node here

131.686 -> and suppose this was pointed to 4

133.686 -> and then here it is pointed to null

135.284 -> suppose we have 4 elements

136.897 -> now how will you reverse it?

137.921 -> can you see this part is already reversed

141.485 -> so we don't have to worry about this part

143.329 -> now let's talk about this part

145.737 -> let's reverse this

146.931 -> but one node can have only one next pointer 77 00:02:29,139 --> 00:02:29,1000 that we have assigned to 1

150.2 -> there is no next pointer here

152.947 -> there is no next pointer here, so

154.159 -> how will you reach to this node?

155.683 -> we have lost the reference to this node

157.401 -> we don't have any reference to this node

159.042 -> so what will we do?

159.947 -> we will take a reference of this node

161.836 -> we will store it to a temporary variable

165.039 -> we will store it in temp

166.265 -> we will always have a reference of this node

168.794 -> now we will try to reverse this part

172.006 -> we will do the same, that we did here

173.827 -> what we did here?

174.658 -> the next for this one should instead of pointing to 4

178.208 -> should point to this

180.535 -> the next of this is pointing to this

182.482 -> now this pointer will be lost

185.567 -> so before loosing this pointer,

187.071 -> we will assign temp to this

190.599 -> so what happens when we assign temp?

192.192 -> as we are pointing the next to the previous one

194.979 -> next node is now pointing to previous

196.663 -> so the next node is getting lost

199.735 -> the node might get lost

200.718 -> in order to not lose it, we store it in temp

203.948 -> we will always have the reference to temp

205.61 -> so now let's try to solve this part

209.38 -> we will say that ok, the next for temp

211.696 -> that the next for temp should point to previous

214.782 -> so first shift the temp & then point it towards the previous

218.492 -> so sometimes what happens here is

221.137 -> people might not understand how to point the next of temp to previous

225.792 -> and also moving temp forward

226.942 -> how is this happening?

227.95 -> so let's see the code for this

229.327 -> you might have understood the logic

230.603 -> when you will code it, you will see ok, this is how we have to solve it

235.101 -> now let's see the same thing being generalised

237.192 -> suppose you have elements from a1 to a n in a linked list

240.473 -> a1, a2, a3, a4, then we have ak & ak+1

243.703 -> last element is a n &

244.759 -> before that we have a n-1

246.354 -> suppose you reversed the part from a1 to aK-1

251.114 -> you reversed it somehow

252.28 -> don't think of how you did it

253.697 -> suppose this part is already reversed

255.882 -> this part is not reversed

257.63 -> this part is as it is

259.067 -> so we have to reverse only this part

261.667 -> this part is already reversed

262.799 -> how will we reverse this part?

264.6 -> what I will do?

266.348 -> I will say that the node before current node will be previous

268.588 -> node before this will be my previous node

271.008 -> 'a k-1' node

273.424 -> what will I do?I will say that instead of pointing to the next,

277.755 -> the next for current will point the previous

279.9 -> next of current will point previous

281.551 -> we already have a pointer for next

283.368 -> now I will move forward one by one

285.813 -> previous will now point here

286.786 -> current will point this &

287.899 -> next will point this

288.929 -> so this way you can see

290.3 -> this part is reversed

291.148 -> initially only this part was reversed

292.521 -> now this part is reversed too

293.906 -> our problem is smaller now

295.934 -> this way you will iterate one by one & move forward

298.793 -> and reverse the front part

300.491 -> then we will make this node head

302.694 -> and you will return it

304.417 -> you must have understood the logic

306.06 -> Let me code it so you can understand it easily

308.052 -> so I have written a very simple code here

310.021 -> sometimes we complicate this simple code

313.009 -> it is not required to complicate so much

315.869 -> it is very simple

317.749 -> we have to reverse, so we started from head

319.386 -> when we take a head, we get a complete linked list

321.834 -> like this

322.669 -> now what we did? current node equals to head

324.867 -> we have to make two pointers

326.245 -> one current node, which will point this right now

328.171 -> this will be our current node

329.737 -> our head node

331.135 -> previous node will be null

332.327 -> the node right before current will be previous node

334.694 -> keep this in mind, we will have a current node, and the one right before it will be previous node

339.399 -> so previous node & current node

340.611 -> previous will be null here

341.779 -> as current node is equal to head here

343.246 -> after that, while current is not equals to null

345.838 -> until our current is not null

346.92 -> what we have to do?

348.032 -> that temp equals to current dot next

350.926 -> we want to save the pointer for this next node

353.672 -> we want that this '4' node should not get lost

357.393 -> because we are going to break this link

359.691 -> if we will break this link, then this node will get lost

361.906 -> before losing this node,

363.459 -> we will save it

364.577 -> so we will save it in temp

367.433 -> so this node is saved in temp

369.089 -> now I can break this link

370.43 -> what will we do? next of current equals to previous

372.309 -> this is current,

373.357 -> next for that, means this node

375.588 -> i will break this link

376.475 -> and this will be equal to previous

377.858 -> so right now, previous was null

379.135 -> so this will point to null now

380.763 -> so the first node will now point to null

383 -> and when our entire linked list is reversed

385.094 -> so this node will become our head

386.756 -> and this will be the last node,

388.414 -> and the next of that will be pointing null

391.577 -> now the next for this is pointing null

394.691 -> now we will move forward

395.666 -> previous will be equal to current

397.057 -> so previous will point this now

401.42 -> and current will be equal to temp

403.499 -> now current is here

405.029 -> instead of this, current will be here

408.803 -> so can you see current is still next to previous

411.183 -> we have just moved one step forward

413.227 -> we broke this link, but

414.781 -> we have the reference for this node,

416.772 -> because we stored it in temp

419.109 -> now let's move forward

419.889 -> then we will check if current is null or not

422.318 -> no current is not null

423.243 -> temp equals to next of current

424.689 -> temp is equal to next of current

426.616 -> so we will change temp,

428.803 -> next of current, which is this node

430.603 -> this is temp now

432.451 -> now this node will be temp

433.727 -> this link will be removed from here

434.839 -> current dot next equals to previous

436.151 -> so we are breaking this link

437.62 -> next of current is not this,

439.974 -> instead of here, next of current will be previous

444.783 -> so next of current is now previous

447.228 -> so you can see that the link is now reversed

449.255 -> after that previous equals to current

451.122 -> we will move forward again

452.825 -> now previous will point this

454.73 -> and current will now point to temp

457.366 -> we moved one step forward

458.914 -> right?

459.86 -> now we will check again,is current null?

461.853 -> no it is not null

463.445 -> so node temp equals to current dot next

465.471 -> so next of current is null

466.886 -> so temp will now point to null

468.319 -> ok?

469.621 -> temp is now pointing null

471.796 -> temp will not be here

472.498 -> current dot next equals to previous

474.351 -> so the next of current will point previous instead of null

477.711 -> it will point this node as this is previous

479.537 -> so next of current is now pointed to previous

481.382 -> so this pointer will now be removed from here

483.188 -> previous equals to current

484.356 -> so current will now be previous

485.542 -> this will be previous

487.225 -> current equals to temp

488.102 -> current will now point to null

490.062 -> as temp is already pointing null

492.419 -> now we will move forward

494.332 -> while current is not equals to null

495.448 -> but now current is pointing to null

497.25 -> so here the loop will be broken

498.971 -> and our linked list is also reversed

500.248 -> 7 is pointing 4, which is pointing 1

503.159 -> & 1 is pointing null

504.976 -> next of 1

505.725 -> so our link is reversed here

507.694 -> the linked list is reversed

509.303 -> after that we are returning previous

510.615 -> as the previous node, will become our head

513.794 -> so this node will become head

515.293 -> so we will return this

516.504 -> so our linked list is reversed here

518.595 -> it was a very simple code

520.102 -> and it handles all our cases

521.912 -> any case you can think of

523.444 -> suppose it was a linked list of one node

525.748 -> so it handles that as well

526.985 -> if the linked list is null

529.104 -> means head is already null

530.451 -> if head would have been null, then current would also be null

532.261 -> so your previous would also be null

533.836 -> and here the loop would have been broken

535.491 -> and you would return null here

536.838 -> then also it would work

537.696 -> if the next of head is null

539.249 -> means you have only one node

541.666 -> then also this loop will work

543.429 -> you can check

544.425 -> even if you have two or fifty nodes,

546.123 -> it will work on all of them

548.086 -> it was a very simple code

549.206 -> now let's see how you can do it recursively

552.171 -> recursively also it would be solved similarly

553.876 -> like we solved it iteratively

555.371 -> ok?

556.291 -> how?

556.833 -> that we will reverse the problem at the front

559.85 -> and then we will break this into a sub problem

563.449 -> we also did this previously in iteration

565.114 -> we solved the first part

566.68 -> so we broke the problem into sub problem

568.712 -> then we have to solve our small sub problem

571.712 -> similarly here,

573.388 -> suppose we reversed this small part

576.73 -> then we will call a recursive function for this part

580.105 -> suppose I reversed this part

583.048 -> then I will again call recursive function for this part

586.626 -> now what is the job of this function?

588.342 -> suppose any recursive function

592.105 -> it's job is to return me a node

595.165 -> and this node will be our head node

597.754 -> of our reversed linked list

598.96 -> means, head node which is this

600.682 -> it will return this node

602.815 -> it will return this

604.096 -> this is the work of a recursive function

605.351 -> to return this node

607.098 -> we will call this new head

609.221 -> this will be our new head

610.682 -> of our new reversed linked list

612.657 -> it's our new head

614.061 -> this is head, this will be our new head

617.027 -> so the work of this recursive function is to return the new head

620.045 -> this will return a new head

622.111 -> it will also reverse it on your own

624.189 -> we don't have to think, how it is reversing this part

627.598 -> we don't have to think of it

628.261 -> it will execute on it's own

630.736 -> and it will change these link to reverse ones

635.045 -> it will do this on it's own

636.246 -> now our job is

637.899 -> now we have to link these two together

640.77 -> the next for this should point this

642.771 -> the next of this should point this

644.44 -> but if you called for this function

646.497 -> and it will return you this pointer

649.613 -> then how will you get this pointer?

651.679 -> how will you get this node?

652.693 -> this is head & let's call this head next

655.272 -> how will we get pointer for this one?

656.976 -> so we can get the pointer from this node

659.23 -> how can we get that?

660.09 -> the next of this head node was this node

663.165 -> we did not loose this pointer

664.983 -> we have saved this pointer

667.058 -> so you found this pointer

668.396 -> so we will point the next of this here

672.257 -> using this, it's next to next will point here only

675.285 -> and the next for this will point this

678.479 -> it will not point this

680.388 -> so your entire linked list is reversed

682.342 -> so these pointers will be gone

685.425 -> can you see your linked list is reversed

687.833 -> so we will code this logic

690.401 -> if you find this confusing then don't worry

692.447 -> once I will code this, you can understand this very nicely

696.296 -> so this is our recursive code

697.753 -> it is also a very simple code

699.192 -> don't get confused here

700.685 -> basically what we are doing here is

702.492 -> you have a head

703.663 -> first we checked, that if head is null

706.005 -> or the next of head is null

707.512 -> then we have to handle that specially

709.945 -> why do we have to handle it specially?

711.514 -> I will tell you later on

712.792 -> first let's understand the main logic

713.973 -> main logic is

714.912 -> that first we called the function for reverse

717.225 -> for head of next

718.792 -> so our head was this

719.864 -> so for it's next we called a recursive function

723.349 -> we called for a recursive function for this part

725.804 -> there I passed head dot next

727.127 -> so I passed this node

728.951 -> and the job of this function is

730.318 -> to reverse it

732.671 -> it is basically calling the same function

734.698 -> it is calling a recursive function

736.489 -> but we will leave it to recursive leap of faith

739.155 -> that it will reverse it on it's own

742.664 -> it will work on it's own & reverse the linked list

746.144 -> and it will return

747.379 -> the pointer for this node

749.582 -> which we will call as new head

754.259 -> the job of this function is to reverse it on it's own

756.559 -> and return new head to me

758.201 -> it did it's job & returned me new head

760.824 -> this is new head

761.741 -> after that what I have to do is

763.873 -> now I know that this is reversed

765.747 -> this part is reversed

767.217 -> now it's next is not pointing to null

768.811 -> the next for this is pointing this

769.989 -> and the next of this is pointing here

772.161 -> next of head is pointing here

774.385 -> now my job is to reverse this pointer

777.424 -> because this much part of the linked list is already reversed

780.712 -> now I will do is, nead next equals to head dot next

783.567 -> means this pointer which was head next

786.674 -> you might remember this was head next

789.03 -> head next which is this pointer,

790.405 -> this will be head next

792.442 -> I will say that head next dot next which is this pointer

795.46 -> the next for this one

796.424 -> the next for this one will point to the head

802.005 -> head next dot next equals to head

805.804 -> next for head next will point to head

807.894 -> after that, the next of head will point to null

810.949 -> now this will point to null

812.129 -> so instead of pointing here,

813.988 -> it will be pointing null

815.516 -> after that I will return new head

818.895 -> this function will return new head

820.901 -> and finally I will get my new head

823.445 -> so you can see that if you keep in mind recursive leap of faith,

826.901 -> then you don't have to think much about it

828.201 -> but if you want to dig deep

830.335 -> if you want to go in deep steps of recursive

833.266 -> so let's see those deep steps

835.205 -> let me take a longer example

836.962 -> then let's see deepy how is it working

839.302 -> suppose this is our example

840.994 -> here the head is currently pointing to 10

843.357 -> first we will check is head null? no it is not

846.362 -> new head equals to reverse of head dot next

848.545 -> so we called the reverse function again

850.9 -> but we called for this one

852.604 -> so now the new function

854.118 -> so first we called the function for reverse

856.53 -> in that head was this node

858.771 -> which has '10'

859.652 -> this function called the next reverse function

863.643 -> but now, it has '5' in it

867.285 -> head dot next has 5 in it

869.595 -> now it will check is head null?

871.633 -> no head is not null

872.638 -> so it will call the function again

874.259 -> and head dot next which was this

876.195 -> the next for this, which is 7

878.384 -> it will call the function again for this one

880.807 -> so reverse function will be called again

881.966 -> but this time it will have element 7

883.66 -> similarly it will call the function again

885.964 -> now, after this

887.843 -> it will call again for head dot next

891.01 -> and at head dot next we have 4

893.492 -> ok?

894.589 -> here we called for this function

895.828 -> now it has 4 in it

897.108 -> now it will check

897.994 -> is head null?

899.02 -> no head is not null

900.185 -> there is '4' in head

901.787 -> then we will check is next of head is null?

903.705 -> so yes the next of head is actually null

905.176 -> the next of this is null

906.345 -> so as the next of this is null,

907.909 -> we will return the head

908.804 -> so this function will return from here

910.015 -> and it will return 4

912.339 -> so can you see that our last element

914.19 -> which is going to be our new head

915.577 -> is being returned

916.993 -> so this element is being returned

918.373 -> and in this function

920.205 -> which was reverse 7

921.397 -> the new head in this function

923.089 -> is the node 4

924.503 -> so new head will be equal to 4

926.811 -> then head next equals to head dot next

928.666 -> so head was this,

929.508 -> head next will be this

930.505 -> then we will say head next dot next

932.494 -> means the next pointer for this one

934.425 -> will point to head

936.341 -> for this function, right now head is this

938.143 -> then, next of head equals to null

940.477 -> the next of head was this, but now instead of pointing here

942.789 -> it will only point to null

944.481 -> so this pointer will be pointing to null here

946.924 -> and this pointer will not be pointing here

949.363 -> so we will get something like this here

951.394 -> and it will return new head

952.692 -> if you remember, new head is still this one

954.444 -> this function again, will return new head

956.877 -> so for this function

959.07 -> which was here,

960.108 -> for this function, new head will be this only

961.95 -> ok?

962.78 -> configuration will be like this

963.879 -> new head will be this only

965.47 -> and then, head next equals to head dot next

968.14 -> so head was this

969.233 -> head next will be this

970.793 -> after that, head next dot next

972.616 -> this is head next

973.646 -> the next for this, will point head

975.629 -> so instead of pointing null,

977.031 -> the next of this will point 5

979.223 -> after that head dot next equals to null

981.459 -> this is head

982.295 -> the next for this, instead of pointing here

984.124 -> it will point null

985.494 -> the next for this will point null

988.239 -> then we will return the new head

989.517 -> new head is this only

990.284 -> so this function got this element as a new head

992.449 -> now what it will do?

993.521 -> new head is this element

996.023 -> head next will be this one

997.918 -> then, head next dot next equals to head

1000.423 -> so the next for this will point here instead of null, as this is head

1005.957 -> after that head dot next equals to null

1008.199 -> so head dot next will not be this

1009.464 -> it will become null

1012.202 -> ok?

1012.872 -> after that we will return new head

1014.647 -> new head was again this element

1016.1 -> so when this function will return

1017.994 -> so it will return this node

1020.847 -> so you can see that the entire linked list is reversed

1023.535 -> and we are returning this node

1026.298 -> which is the new head in our reversed linked list

1029.512 -> so this is going to be our head

1031.26 -> and our linked list is also reversed

1032.809 -> so this is how it works

1034.338 -> otherwise we don't have to go in such depth

1036.42 -> we don't have to go in so much depth

1038.576 -> I have explained this but

1040.165 -> always focus on understanding the recursive leap of faith

1042.6 -> if you want to understand recursion even better

1044.728 -> then I have already made a video on recursion in DSA One Course

1048.568 -> there you can understand recursion better

1051.928 -> there are multiple videos

1053.309 -> and I have explained recursive leap of faith there through multiple examples

1056.765 -> do check it out

1057.971 -> you will understand recursion properly

1059.499 -> my gaurantee

1060.653 -> so this question is solved here

1063.313 -> after this we will be solving multiple questions in linked list

1065.716 -> in our upcoming videos

1066.421 -> if you liked it, then do like this video

1068.845 -> also subscribe to the channel

1069.647 -> see you in the next video. Bye Bye.

Source: https://www.youtube.com/watch?v=ugQ2DVJJroc