Linked List

[00:00:00]
>> Bianca Gandolfo: Here are some things that you usually do as linked lists. So we talked about deleting a little bit earlier. So delete a node in the middle of a linked list. So the question here is, how do you find the middle of a linked list? How you do this is basically you need to get the length of the linked list.

[00:00:18]
You can keep track of this. So this concept of doing it ahead of time, or doing it like when you need it. So if you, for example, as you add in those into your linked list, you kept the size, right? The middle would be easy cuz you could just use subtraction.

[00:00:37]
But if you don't then you would need to calculate that. So, how do you calculate the length of a link list? Is you just have to loop through it, that while loop that I showed you, that's the typical way of looping through a link list. And then you would find the length, you would divide that by two, and then you would loop again to get to the middle.

[00:00:59]
And so that's how you get to the middle of a link list. So if you wanna delete a duplicate you need to track duplicates, if you use an auxiliary data structure like hash table, that would be pretty easy. And you could also duplicate, so when you're deleting a duplicate, a rule of thumb, depending on the data structure is, so there are a few ways you can do it.

[00:01:29]
Using a hash table's easy cuz you just loop through and you save everything through the hash table. If it's already saved in the hash table, the you know you've already seen it. The other thing you can do is you can sort the data structure with a link list, it's kind of a hard data structure to sort.

[00:01:47]
It is possible, but it's not a typical question you will see in an interview. If it is something, it would be like a very hard interview I would say. But you could like merge, sort and link list. Or you can ask, is this already sorted? If it's duplicate question is already sorted, great, that's easy because then it's just a linear time thing where you just loop through.

[00:02:12]
If there are two values next to each other that are the same, you just delete one. If you're going to sort it, whenever you're sorting automatically think, and n/logn. Because sorting on average is gonna be n/logn, with like the job script dot sort method, you can assume that would be the time complexity of that algorithm.

[00:02:38]
So there's that, otherwise,
>> Bianca Gandolfo: Yeah, those are the things I think about when deleting duplicates. It's not just gonna be on a link list there's duplicates. And erase those duplicates and yeah, those are the main ones strings. Strings and Arrays, and Linked List, and duplicates are the main ones.

[00:03:03]
Hash Tables you won't ever have a duplicate. Stack / Queue you don't really do a lot of traversing and searching inside of stack and a queue you can. But it's not like the main reason you would even use that data structure. So you would see that more with an array question.

[00:03:23]
Cool, so reversing a link list. Basically, you need to remember how we deleted the second to last node? That technique is really similar to reversing a link list, is that you need to get the one before each one, if that makes sense. Or what you can do is you can have two pointers, and then you can swap.

[00:03:49]
So a lot of these link list questions assume that you have two pointers. One being a slow pointer and one being a fast pointer. So the fast pointer goes twice as fast than the slow pointer, typically. And so, this one is for kth to the last node in the linked list cycle is like the classic problems for a two pointer linked list.

[00:04:09]
So if you wanna see if a linked list contains a cycle, what you do is you start your pointer. Let's go to a picture. You start your pointer, your slow pointer, would just move one, and your fast pointer moves two. So slow pointer starts here, and then fast pointer starts here, it goes two.

[00:04:33]
This is a w length and so it's not that helpful. But essentially, if the fast pointer and the slow pointer ever are in the same node, that means that you have cycle so that's the trick for that. And then, for the kth to the last node, assuming you don't already know the length, what you can do is you can have your first pointer be at zero.

[00:05:03]
Or at the head, and then your second pointer be at the head plus k. And then, you loop both of them at the same pace. When your second pointer gets to the last one, your first pointer is at the kth to the last one. Does that make sense, kind of?

[00:05:27]
>> Speaker 2: Yeah, inner outer, kinda like-
>> Bianca Gandolfo: No, it's actually linear, so every time you loop you're just moving them at the same time. So it's always like, i + 1, i+ 1. Once one hits null, you know that this one is going to be k places behind because you're just looping them at the same speed.

[00:05:48]
If there's only one loop, so it's a linear solution. So it's pretty good.